Zenn
💨

【Python】スライディングウィンドウ法について(1)

に公開
1
Python
substring
subarray
tech

スライディングウィンドウ法とは

こんにちは！アルゴリズムの問題を解いていく中で、スライディングウィンドウ法について触れる機会があったのでまとめていきたいと思います。スライディングウィンドウ法は、連続するデータ（配列・文字列など）に対して、効率的に部分問題を解く手法です。特に、「連続する部分配列（subarray）や部分文字列（substring）に関する問題」 に適しています。通常、2つのポインタ (left と right) を用いてウィンドウを動的に調整しながら解を求めます。

スライディングウィンドウの種類

スライディングウィンドウの種類について、以下の表にまとめたいと思います。

種類 特徴 使用例
固定サイズ ウィンドウのサイズが一定 部分配列の最大和・最小和、移動平均
可変サイズ 条件に応じてウィンドウを伸縮 ある条件を満たす最短の部分列、異なる文字を含む最長の部分文字列

固定サイズのスライディングウィンドウ(長さkの部分配列の最大和)

問題
長さ n の整数配列 nums が与えられたとき、長さ k の連続部分配列の最大和を求めよ。

def max_subarray_sum(nums, k):
    if not nums or k > len(nums):
        return None  # 無効な入力

    # 初期ウィンドウの合計を計算
    current_sum = sum(nums[:k])
    max_sum = current_sum

    # スライディングウィンドウを移動しながら最大和を更新
    for i in range(k, len(nums)):
        current_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, current_sum)
    return max_sum

# 使用例
nums = [2, 3, 5, 1, 6, 2, 8, 1]
k = 3
print(max_subarray_sum(nums, k))  # 出力: 16 (部分配列 [6, 2, 8])

ポイント

  • スライディングウィンドウを1つ右に移動しながら、次の要素を追加し、前の要素を引くことで効率よく更新。

可変サイズのスライディングウィンドウ(和がS以上となる最小の部分配列)

問題
正の整数配列 nums と整数 S が与えられたとき、部分配列の和が S 以上になる最小の長さを求めよ。

from typing import List 

def min_subarray_len(S: int, nums: List[int]) -> int:  # List[int] を使う
    left = 0
    total = 0
    min_length = float('inf')

    for right in range(len(nums)):
        total += nums[right]

        while total >= S:
            min_length = min(min_length, right - left + 1)
            total -= nums[left]
            left += 1

    return min_length if min_length != float('inf') else 0

# 使用例
nums = [2, 3, 1, 2, 4, 3]
S = 7
print(min_subarray_len(S, nums))  # 出力: 2

ポイント

  • right を動かしながら部分配列の合計を増やし、条件を満たしたら left を進めて範囲を狭める

その２へ

長くなったので、(2)へ行きます！
https://zenn.dev/daichi09167/articles/eeb76a9810f37c

1

Discussion