什么是 sliding-window 技术？

Question

IT Interview Practice · Accepted Answer

**sliding-window** 技术在数组或字符串上维护一个连续的范围（window），并通过滑动而不是从头重新计算来解决许多 subarray/substring 问题，时间复杂度为 **O(n)**。

## 核心思想

通过移动右边界来扩展窗口；当违反约束时通过移动左边界来收缩窗口。复用之前的计算结果，而不是重新扫描。

## 示例：大小为 k 的任意窗口的最大和

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

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

## 时间复杂度

- **时间:** O(n) — 每个元素恰好进入和离开窗口一次。
- **空间:** fixed windows 为 O(1)，追踪内容时为 O(k)。

## 何时使用 / 常见陷阱

用于"具有性质 X 的最长/最短/最大 subarray"类问题。对于 **variable** 窗口，前移左指针以恢复约束。添加/移除边界元素时要注意 off-by-one 错误。

## 为什么这很重要

Sliding window 消除了冗余工作，将 O(n·k) 的重新计算转变为一次遍历。

它是处理 substring 和 subarray 问题的标志性模式，这类问题在面试中频繁出现。

这种洞察——复用之前的结果而不是重新计算——推广到了流式处理和实时数据处理。

核心思想

示例：大小为 k 的任意窗口的最大和

相关问题

时间复杂度

何时使用 / 常见陷阱

为什么这很重要