滑动窗口到底什么时候用？从连续区间到边界单调性

初学滑动窗口时，最容易形成一种模糊印象：题目只要出现“连续子数组”或“连续子串”，似乎就应该架起两个指针。真正做题时却很快遇到反例：无重复字符的最长子串可以滑，和为 K 的子数组却常常不能滑；最小覆盖子串在“已经满足”时收缩，最长合法子串又在“不满足”时收缩。

这些差异并不靠题感解决。滑动窗口背后有一套可以推导的判断标准：

滑动窗口是利用边界单调性，对连续区间进行增量枚举和剪枝。

理解“连续区间”“增量维护”和“边界单调性”这三个词，就能回答两个最重要的问题：什么时候能用滑动窗口，以及窗口究竟应该在什么条件下收缩。

一、滑动窗口究竟在做什么

设当前窗口为闭区间 [left, right]。算法不断执行两种操作：

1. right 向右移动，把一个新元素加入窗口；
2. 必要时移动 left，把左端元素移出窗口。

如果每个元素最多进入窗口一次、离开窗口一次，两个指针总共只移动 O(n) 次。因此，即使代码中有一个嵌套的 while，总时间复杂度仍然通常是 O(n)，而不是 O(n²)。

它比暴力枚举快的原因，并不是“用了两个指针”，而是它敢于一次排除一批不可能成为答案的区间。例如窗口已经包含三个不同元素，而题目最多允许两个，那么在右端点不变的情况下，继续保留当前左边界没有意义，只能向右收缩。

二、“连续区间只是必要信号”是什么意思

在普通滑动窗口讨论中，可以把两个命题记为：

• A：这道题适合用普通滑动窗口；
• B：题目研究的候选对象是连续子数组或连续子串。

通常有 A → B，但没有 B → A。也就是说，使用滑动窗口时研究的通常是连续区间；但研究连续区间的题，不一定能使用滑动窗口。

例如下面三道题都研究连续区间：

• 3. 无重复字符的最长子串：适合滑动窗口；
• 560. 和为 K 的子数组：允许负数，通常使用前缀和与哈希表；
• 5. 最长回文子串：通常使用中心扩展或动态规划。

所以“连续”只是第一道筛选。对于可变长度窗口，还需要检查窗口状态能否增量维护，以及左右边界是否具有单调性。

三、滑动窗口成立的三个条件

1. 候选对象具有连续性

窗口只能表达 [left, right] 这样的连续区间。若题目允许跳过中间元素，例如最长递增子序列，就应该优先考虑动态规划、贪心或二分，而不是滑动窗口。

注意，题目不一定要求返回某个区间。它也可能要求统计符合条件的连续子数组数量，但被统计的候选对象仍然是连续区间。

2. 窗口状态可以增量维护

加入或删除一个元素后，应当能够较快地更新状态，而不是重新扫描整个窗口。常见状态包括：

• 元素总和、乘积；
• 字符或数字的出现次数；
• 不同元素数量；
• 0、奇数或“不合格元素”的数量；
• 已经满足要求的字符种类数。

频次表、哈希表、计数器和单调队列，都是用来维护窗口状态的工具。它们不是滑动窗口成立的原因，只是让“加入右端、删除左端”足够高效。

3. 边界具有单调性

这是最关键、也最容易被忽略的条件。

当 right 不断向右时，我们必须能够确信：已经被 left 越过的位置，以后不需要重新成为左边界。换句话说，left 只能向右，不能回头。

以“窗口内至多 K 个不同元素”为例：如果一个窗口因为不同元素太多而非法，那么继续扩大它不会自动减少种类；删除左端元素则可能让它恢复合法。更进一步，固定 right 后，一旦 [left, right] 合法，删除更多左端元素得到的更短窗口也仍然合法。合法左边界形成一段连续区域，算法只需要维护这段区域的边界。

这就是边界单调性。判断它时，可以问自己一句：

右端加入元素后，如果条件被破坏，持续删除左端元素是否一定朝恢复条件的方向前进？

如果答案是否定的，普通双指针滑动窗口通常就没有可靠的收缩方向。

四、不要背收缩条件，先定义窗口不变量

精确拿捏滑动条件的方法，是先写出窗口的合法性谓词 P(window)，也就是“什么样的窗口算合法”。随后根据题目目标决定收缩方向。

最长合法窗口

目标是让窗口尽可能大，所以只在窗口非法、不得不收缩时移动左端点：

left = 0
for right in [0, n):
    将 right 加入窗口
    while 窗口不合法:
        将 left 移出窗口
        left += 1
    answer = max(answer, right - left + 1)

最短满足窗口

目标是让窗口尽可能小。窗口一旦满足要求，就要趁机不断删除左端元素，直到再删便不满足：

left = 0
for right in [0, n):
    将 right 加入窗口
    while 窗口已经满足要求:
        answer = min(answer, right - left + 1)
        将 left 移出窗口
        left += 1

因此，“最长题在非法时缩、最短题在合法时缩”不是两套互相矛盾的口诀，而是由优化目标自然推导出来的。

五、把限制条件翻译成“违规成本”

大量最长窗口题都能统一写成：

窗口的违规成本 <= 预算 K

于是收缩条件一般就是 while 违规成本 > K。这种表达比记忆每道题的代码更稳定，因为你是在维护一个明确的不变量。

六、典型题目逐题推导

例 1：3. 无重复字符的最长子串

窗口合法条件是“每个字符最多出现一次”。加入 s[right] 后，只有这个新字符可能造成冲突，因此可以写：

freq[s[right]] += 1
while freq[s[right]] > 1:
    freq[s[left]] -= 1
    left += 1
answer = max(answer, right - left + 1)

这里求的是最长合法窗口，所以在“出现重复、窗口非法”时收缩，恢复合法后更新最大长度。

例 2：1004. 最大连续 1 的个数 III

题目允许把最多 k 个 0 改成 1。把“修改次数”看成预算，则违规成本就是窗口中的 0 数量：

合法条件：zeroCount <= k
收缩条件：while zeroCount > k

删除左端元素不会让 0 的数量增加，因此收缩方向明确。这道题和 904. 水果成篮 本质相同，后者只是把条件换成 distinctCount <= 2。

例 3：424. 替换后的最长重复字符

若想把整个窗口变成同一个字符，最省的做法是保留窗口内出现次数最多的字符，替换其余字符：

replacementCost = windowLength - maxFrequency
合法条件：replacementCost <= k
收缩条件：while replacementCost > k

这道题真正困难的不是双指针，而是正确写出“至少需要替换多少次”。一旦成本公式确定，窗口条件就随之确定。为了先保证概念准确，可以根据 26 个大写字母的频次重新计算 maxFrequency；熟悉证明后，再使用只增不减的历史最高频次优化常数。

例 4：209. 长度最小的子数组

数组元素都是正整数，扩张右端只会让 sum 增大，删除左端只会让 sum 减小，因此总和具有需要的单调性。

满足条件：sum >= target
while sum >= target:
    answer = min(answer, right - left + 1)
    sum -= nums[left]
    left += 1

注意这里在“窗口合法”时收缩，因为题目求的是最短满足窗口。正数限制不是装饰条件；如果允许负数，收缩对总和的影响方向就不再确定。

例 5：76. 最小覆盖子串

这道题的窗口状态不是简单的长度或总和，而是字符覆盖关系。可以维护：

• need[c]：目标字符串需要字符 c 多少次；
• window[c]：当前窗口包含字符 c 多少次；
• formed：已经达到所需频次的字符种类数；
• required：目标字符串中的不同字符种类数。

窗口满足条件是 formed == required。因为要求最短覆盖，所以每次满足后都更新答案并尝试删除左端；若某个必需字符的频次从“刚好足够”降到“不足”，就减少 formed，停止收缩并继续扩张右端。

例 6：438. 找到字符串中所有字母异位词

异位词长度必定等于 p.length，因此这是固定长度窗口：

加入 right
若窗口长度 > p.length，则移出 left
若窗口长度 == p.length 且频次相同，则记录 left

固定窗口不需要通过合法性决定左端点，左端点由窗口长度唯一确定。它仍属于滑动窗口，但不依赖可变窗口中的“非法后收缩”逻辑。

例 7：713. 乘积小于 K 的子数组

数组元素均为正数，窗口乘积过大时，删除左端因子会让乘积不增，因此可以收缩到 product < k。当 [left, right] 合法时，以 right 结尾的这些窗口都合法：

[left, right], [left+1, right], ..., [right, right]

一共有 right - left + 1 个，所以每轮把这个数量加入答案。另需单独处理 k <= 1：正整数乘积不可能小于 1，答案为 0。

例 8：992. K 个不同整数的子数组

“至多 K 种”具有清晰的单调性，但“恰好 K 种”的合法左边界不方便直接用一个窗口统计。可以利用集合关系：

恰好 K 种 = 至多 K 种 - 至多 K-1 种
exactly(K) = atMost(K) - atMost(K - 1)

atMost(K) 中，每次把窗口恢复到不同元素数量不超过 K 后，累加 right-left+1。这个转换也常用于“恰好 K 个奇数”等计数问题。

七、为什么有负数时普通求和窗口经常失效

看 560. 和为 K 的子数组。假设数组为 [1, 4, -2]，目标为 3，整个区间的和正好是 3。

如果在读到 4、发现当前和为 5 时，套用“总和过大就收缩”，就可能先后删除 1 和 4。之后再读到 -2，已经无法让 left 回到开头，于是漏掉 [1, 4, -2]。

根源是：

• 加入右端元素，和可能增大，也可能减小；
• 删除左端元素，和也可能增大或减小；
• sum > target 不再意味着“左端应该右移”。

此时应使用前缀和。若 prefix[j] - prefix[i] = k，只需查询此前是否出现过 prefix[j] - k，因此 LeetCode 560 的标准方法是前缀和加哈希表。

862. 和至少为 K 的最短子数组 同样允许负数，普通窗口也会失去总和单调性。它使用前缀和加单调队列，在前缀和序列上维护有价值的候选左边界。

这并不是说“出现负数就永远不能滑动”，而是说：如果你的收缩判断依赖总和随扩张或收缩单向变化，那么负数会破坏这项证明，必须重新寻找结构。

八、其他“连续但不适合普通滑窗”的题

这些题说明，不能只凭“连续”两个字决定算法。真正要寻找的是：问题是否存在一个可以不断前移、永不回退的边界。

九、最容易写错的五个细节

1. 把 while 写成 if

加入一个新元素后，窗口可能需要删除多个左端元素才能恢复合法。例如无重复子串中，新字符可能和很早以前的字符重复。除非能证明每轮最多只需删除一个元素，否则使用 while。

固定长度窗口在稳定阶段每轮只超长 1，因此可以使用 if；写成 while 通常更统一。

2. 在错误的时机更新答案

• 最长合法窗口：恢复合法后更新；
• 最短满足窗口：满足条件时、删除左端之前更新；
• 固定窗口：长度恰好满足时检查；
• 计数窗口：恢复合法后计算当前右端点的贡献。

3. 删除元素后忘记维护派生状态

例如用哈希表维护不同元素数量时，某个频次降到 0 后要删除键或减少 distinctCount。覆盖子串中，必需字符从足够变为不足时要减少 formed。

4. 忽略题目对元素取值的限制

正数、非负数、二进制数组、仅含大写字母等条件，往往正是单调性或低成本状态维护成立的原因。条件变化后，原模板可能立即失效。

5. 看到“恰好”就强行维护一个窗口

“至多”通常比“恰好”更有单调性。计数题遇到“恰好 K 个”时，应优先尝试 atMost(K) - atMost(K-1)，或寻找前缀和等其他等式转换。

十、做题时的完整判断清单

面对一道新题，可以按以下顺序思考：

1. 候选答案是否围绕连续子数组或连续子串？如果不是，通常先排除滑动窗口。
2. 是固定长度还是可变长度？固定长度通常直接维护加入和移出。
3. 加入右端、删除左端时，窗口状态能否快速更新？
4. 用一句准确的话写出“合法窗口”或“满足要求的窗口”。
5. right 扩张后若条件被破坏，删除左端是否持续朝恢复条件的方向前进？
6. 已经越过的左端位置，未来是否可能还需要回来？如果需要，普通滑动窗口不成立。
7. 求最长合法、最短满足、固定长度，还是统计数量？这决定答案更新与收缩时机。
8. 题目中的正数、非负数、字符集大小等限制，是否是单调性成立的前提？

最后可以把最常见的三类题压缩成三句话：

求最长：窗口非法就缩，恢复合法后更新。

求最短：窗口合法仍要缩，在收缩过程中更新。

求数量：先维护单调的“至多”条件，再计算右端点贡献或作差得到“恰好”。

但口诀只能帮助回忆，不能替代证明。真正可靠的切入点始终是：先定义窗口不变量，再确认边界只会向一个方向移动。只要这两件事能够说清楚，滑动条件通常就不需要猜。