配列のスライディングウィンドウテクニックの使い方

例えば、配列内の連続する要素の和や積を計算したり、特定の条件を満たす部分配列を見つけたりする場合にスライディングウィンドウテクニックが役立ちます。

以下に、スライディングウィンドウテクニックのいくつかの具体的な使用例とコード例を示します。

1. 配列内の連続する要素の和を計算する例:

def sliding_window_sum(arr, k):
    window_sum = sum(arr[:k])
    result = [window_sum]
    for i in range(k, len(arr)):
        window_sum = window_sum + arr[i] - arr[i - k]
        result.append(window_sum)
    return result
# 使用例
arr = [1, 2, 3, 4, 5, 6, 7]
k = 3
result = sliding_window_sum(arr, k)
print(result)  # Output: [6, 9, 12, 15, 18]

2. 配列内の特定の条件を満たす部分配列を見つける例:

def find_subarrays_with_sum(arr, target_sum):
    left = 0
    current_sum = 0
    result = []
    for right in range(len(arr)):
        current_sum += arr[right]
        while current_sum > target_sum:
            current_sum -= arr[left]
            left += 1
        if current_sum == target_sum:
            result.append(arr[left:right+1])
    return result
# 使用例
arr = [1, 2, 3, 4, 5, 6, 7]
target_sum = 9
result = find_subarrays_with_sum(arr, target_sum)
print(result)  # Output: [[2, 3, 4], [4, 5]]

これらはスライディングウィンドウテクニックの一部の例ですが、さまざまな問題に応用することができます。具体的な問題に対して最適なアプローチとコードを作成するためには、問題の要件に応じて適切なアルゴリズムを選択し、必要に応じてスライディングウィンドウテクニックを組み合わせる必要があります。