sliding-window technique とは何ですか？

Question

IT Interview Practice · Accepted Answer

**Sliding-window** technique は、array や string 上の contiguous range（window）を保ち、毎回 recompute せずに slide させることで、多くの subarray/substring problem を **O(n)** で解きます。

## 考え方

right edge を動かして window を expand し、constraint が破れたら left edge を動かして shrink します。前回の computation を reuse し、再 scan を避けます。

## 例: size k の window の最大 sum

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # first window の sum
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # new を add し old を drop
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## Complexity

- **Time:** O(n) — each element は window に 1 回入り 1 回出る。
- **Space:** fixed window なら O(1)、contents tracking では O(k)。

## いつ使うか / pitfalls

"longest/shortest/max subarray with property X" の問題に使います。**variable** window では constraint を回復するため left pointer を進めます。boundary element の add/remove で off-by-one に注意します。

## なぜ重要なのか

sliding window は redundant work を消し、O(n·k) recomputation を one pass に変えます。substring/subarray problem の go-to pattern であり、previous result を reuse する insight は streaming や real-time data にも一般化できます。

考え方

例: size k の window の最大 sum

Complexity

いつ使うか / pitfalls

なぜ重要なのか

関連する質問