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

3.1 スライディングウィンドウ法の定義。

スライディングウィンドウ法 (Sliding Window) — は、配列や文字列の課題を解決するためのテクニックで、 固定された部分配列（または部分文字列）をデータに沿って動かし、 最適な解決法を見つけることを目的としています。これは、固定サイズのウィンドウ内の要素を処理し、 課題の条件に応じてウィンドウを動的に変更することができます。

このテクニックは特に配列や文字列のようなデータシーケンスに関連する問題に役立ち、 より単純なアプローチと比較して時間計算量を減少させるのに役立ちます。

基本原則

• ウィンドウの初期化: ウィンドウの開始位置と終了位置を設定します。
• ウィンドウの移動: ウィンドウの境界を順次移動し、一方の要素を追加し、 もう一方の要素を削除します。
• ウィンドウの処理: 現在のウィンドウで必要な計算を各ステップで行います。

スライディングウィンドウ法の時間と空間計算量

時間計算量:

• O(n) — 多くの場合、ポインタまたはウィンドウが配列を線形に移動して、 ウィンドウの可能な位置をすべてチェックするためです。

空間計算量:

• O(1) — 現在の値を格納するために、固定数の追加メモリを使用する場合。
• O(k) — 現在のウィンドウ内に要素を格納する必要がある場合、ウィンドウサイズは k。

3.2 部分配列の最大合計を見つける。

固定サイズ部分配列の最大合計を見つける方法

課題:

最大の合計を持つ固定サイズの部分配列kを見つける。

解決法:

スライディングウィンドウ法を利用して、現在の部分配列の合計を保持し、 ウィンドウを移動させるとともに最大合計を更新します。

時間計算量: O(n).

Pythonの例:

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1
            
    window_sum = sum(arr[:k])
    max_sum = window_sum
            
    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
            
    return max_sum
        
        

3.3 文字列中の全てのアナグラムを探す

課題:

文字列sの中で与えられた部分文字列pのアナグラムを全て見つける。

解決法:

スライディングウィンドウ法を利用して現在のウィンドウの文字の頻度辞書を保持し、 それを部分文字列の頻度辞書と比較します。

時間計算量: O(n).

Pythonの例:

from collections import Counter

def find_anagrams(s, p):
    p_count = Counter(p)
    s_count = Counter()
                
    result = []
    k = len(p)
                
    for i in range(len(s)):
        s_count[s[i]] += 1
        
        if i >= k:
            if s_count[s[i - k]] == 1:
                del s_count[s[i - k]]
            else:
                s_count[s[i - k]] -= 1
                            
        if s_count == p_count:
            result.append(i - k + 1)

    return result
        

3.4 最小部分配列を見つける

指定された値を超える合計を持つ最小部分配列を見つける

課題:

要素の合計が指定された値Sを超える最小の部分配列を見つける。

解決法:

スライディングウィンドウ法を使用して、合計がSを超えるまで右境界を拡張し、 その後、部分配列の長さを最小化するために左境界を移動します。

時間計算量: O(n).

Pythonの例:

def min_subarray_len(S, arr):
    n = len(arr)
    min_len = float('inf')
    current_sum = 0
    left = 0
            
    for right in range(n):
        current_sum += arr[right]
                
        while current_sum >= S:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
            
    return 0 if min_len == float('inf') else min_len