**滑动窗口（Sliding Window）**是一种处理数组和字符串子区间问题的常用技巧。它通过维护一个由 left 和 right 定义的窗口，将很多 $O(n^2)$ 的双重遍历优化到 $O(n)$。
核心思想
right向右移动：把新元素纳入窗口。left向右移动：把不再需要的元素移出窗口。- 在移动过程中，维护窗口状态（如和、计数、最大值）并更新答案。
从暴力到滑窗的关键在于：相邻窗口高度重叠，只需要增量更新，而不需要每次重算整个区间。
适用场景
- 最长/最短满足条件的子数组或子串。
- 判断一个字符串是否覆盖另一个字符串（如最小覆盖子串）。
- 统计满足条件的子数组/子串个数。
- 固定长度区间统计（和、平均值、最大值、最小值）。
两类窗口
固定窗口（Fixed Window）
窗口大小固定为 $k$，适合“每连续 $k$ 个元素”的问题。
- 先计算前 $k$ 个元素的初始状态。
- 每次右移一格：加入新元素，移除旧元素。
- 持续更新答案。
可变窗口（Variable Window）
窗口大小根据条件动态变化，常见于“最短/最长满足条件子串”。
right持续扩张窗口。- 当窗口满足（或不满足）条件时，移动
left收缩。 - 在扩张和收缩过程中记录最优解。
常用模板
Go 模板（可变窗口）
func slidingWindow(s string) int {
left, right := 0, 0
window := make(map[byte]int)
res := 0
for right < len(s) {
c := s[right]
right++
window[c]++
for windowNeedsShrink {
d := s[left]
left++
window[d]--
}
// 根据题目更新 res
}
return res
}
为什么通常是 $O(n)$
设数组长度为 $n$：
right最多从0走到n-1，共 $n$ 步。left也只会单调右移，最多 $n$ 步。
因此总操作数满足：
$$ T(n) \le n + n = 2n = O(n) $$
这本质上依赖“指针不回退”的单调性，等价于对 $O(n^2)$ 搜索空间做了大量剪枝。
进一步优化手段
- 哈希表：维护频次、去重、覆盖关系。
- 前缀和：快速处理区间和与计数问题。
- 单调队列：优化滑动窗口最大值/最小值。
- 固定窗口预判：窗口长度固定时，优先用“入一出一”的 $O(1)$ 更新。
LeetCode 典型题
按套路整理，练的时候建议先做固定窗口，再做可变窗口，最后做单调队列。
固定窗口
可变窗口
单调队列（窗口最值）
使用时的检查清单
开始写代码前，先明确这 4 件事：
- 窗口里维护的状态是什么？
- 什么时候扩张窗口？
- 什么时候收缩窗口？
- 在哪个时机更新答案？
只要这四点清晰，绝大多数滑动窗口问题都能稳定落地。