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, , , , , ], )
时间复杂度
- 时间: O(n) — 每个元素恰好进入和离开窗口一次。
- 空间: fixed windows 为 O(1)，追踪内容时为 O(k)。
何时使用 / 常见陷阱
用于"具有性质 X 的最长/最短/最大 subarray"类问题。对于 variable 窗口，前移左指针以恢复约束。添加/移除边界元素时要注意 off-by-one 错误。
为什么这很重要
Sliding window 消除了冗余工作，将 O(n·k) 的重新计算转变为一次遍历。
它是处理 substring 和 subarray 问题的标志性模式，这类问题在面试中频繁出现。
这种洞察——复用之前的结果而不是重新计算——推广到了流式处理和实时数据处理。