先记住这个答案
当右指针扩展使窗口第一次满足条件时启动收缩:记录当前窗口长度;然后右移左指针,每移一步若窗口仍满足条件就更新最短长度并继续,直到条件不再满足或窗口为空。这样收缩依赖单调性,左指针只向右不回退,因此不会漏掉更优解,整体复杂度是 O(n)。
- 满足条件后立即尝试收缩左指针
- 收缩过程中逐步更新最短窗口
- 左指针单调右移才能保证不错过最优
收缩时的核心判断规则
可变滑动窗口求最短解时,右指针不断外扩使窗口从“不满足”变为“满足”。一旦条件成立,当前窗口就是右端为 i 时的一个候选解,也是可能继续缩短的起点。此时应让左指针向右逐个试探。每次移动前先记录当前满足条件的窗口长度,然后减去原左端值并右移左指针;移动后若窗口仍未失去条件,说明还能更短,继续重复记录与移动。只有当条件破裂后,才停止本轮收缩并继续外扩右指针。
收缩不影响最优性的根本原因在于性质的单调方向。典型的正整数求和问题里,窗口总和随扩展右端只增不减,因此右端越靠右,满足“和≥target”所需的最小左端只会向右或不动,绝不会回退。所以每一个被右移过的左端点都不会再与更远的右端构成更优答案,双指针可以线性推进;收缩中每一步都更新,即使最佳窗口恰好出现在收缩到一半时,也能被记录下来。
const minSubArrayLen = (target, nums) => {
let left = 0;
let sum = 0;
let best = Infinity;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
best = Math.min(best, right - left + 1);
sum -= nums[left];
left++;
}
}
return Number.isFinite(best) ? best : 0;
};
console.log('target=7, [2,3,1,2,4,3]:', minSubArrayLen(7, [2,3,1,2,4,3]));
console.log('target=7, []:', minSubArrayLen(7, []));
console.log('target=2, [1,3,1]:', minSubArrayLen(2, [1,3,1]));
console.log('target=5, [1,2,2]:', minSubArrayLen(5, [1,2,2]));查看输出与解释
target=7, [2,3,1,2,4,3]: 2
target=7, []: 0
target=2, [1,3,1]: 1
target=5, [1,2,2]: 3时间复杂度 O(n),空间 O(1)。每个元素最多进入窗口一次、离开窗口一次。空数组或无法达到目标时返回 0。
网络请求日志中定位最短高峰窗口
假设某服务每分钟请求计数为 [7,1,2,3,5,4],运维想找到总请求数至少达到 10 的最短连续分钟段。右指针从 0 起累加,到索引 2 时总和为 10,第一次满足条件,于是立即收缩。先记录长度 3(索引 0 到 2),左移移除 7 后总和变 3,不满足,收缩停止;随后右指针继续扩大窗口。最终在索引 4 到 5 之间收缩出长度 2 的窗口吗?实际模拟得到最优是索引 2 到 4 的长度 3,算法输出 3。
这个场景说明每删除一个左边界前都要记录当前长度,不能等一次性删到不能再删才记录。因为删掉 7 后窗口不满足了,但如果之前没有记录长度 3,就可能漏掉以索引 0–2 为右端点终点的候选解。虽然它不是最优,但无法提前知道。更关键的是,当后续右指针到索引 3 时,我们又需要重新评估收缩,直到找到最短为 3 的解。
什么情况下不能这样收缩
本文方法的前提是窗口状态关于扩展具有单调性:右端外扩会使“满足目标”从假变真,但不会从真变假。正整数数组和 ≥ target 满足这点,覆盖目标字符类问题中增加字符不会让已覆盖集合消失,也满足。但若数组中存在负数,总和可能因扩展右端而下降,原本满足的窗口可能变成不满足,左指针对应的最小可行位置不再单调,继续使用这种收缩会错失解。
面对负数,需要换用前缀和加单调队列,或采用二分长度检查等代价更高的算法;全零元素通常不破坏单调性,但会延长收缩过程的时间。另一个边界是当数组本来就无法满足条件时,需要显式返回 0。示例中的空数组或所有正数之和仍小于 target 都应落到这个分支,避免把 Infinity 当结果返回。
容易答错的地方
- 收缩时只记录最终状态
- 有人会在 while 中直接跳过被删元素,等 left 停在第一个不满足的位置后才记录一次。但最短窗口可能出现在删除一步或几步后、还未破坏条件时;丢失中间记录会直接漏解。正确做法是在每次删除前都记录当前满足条件的长度。
- 条件破坏后继续收缩
- 有人为了让窗口更短,会在窗口已经不满足后还继续右移 left,认为之后右端加入元素时可能再达标。这不会得到合法的候选解,还会把左指针推得过远;即使后续重新满足,可能需要回退左指针,但单调假设下回退是多余的,继续推更会错过正确起点。应该在 while 条件为假时立刻停止本轮收缩。
面试官还会怎么问?
为什么收缩完成的左指针在后续扩展中不需要回退?
因为条件具有单调性:右端外扩只会让窗口状态更容易满足,因此满足条件所需的最左下标也只能向右移动,不会向左。所以每个左指针一旦被移出窗口,就不会再参与到更优的窗口组合里,可以放心继续向右推进。
最小覆盖子串问题的收缩条件与和值问题有何不同?
和的对比用数值 sum 比较简单;覆盖子串需要记录目标字符的剩余计数,并统计当前还缺多少种字符。当“缺失种类数”为 0 时,就相当于条件满足,可以收缩左指针,每次移动后若移除的字符导致某些字符不够,则重新进入不满足状态。判断方法换成哈希表,收缩框架一致。
数组中有 0 或负数时分别怎么处理?
0 不会破坏单调非减,可继续用本方法,但可能在收缩时总和不变,循环多执行几次。负数会让扩展右端可能减少总和,单调性不成立,不适合双指针收缩;应改用前缀和相关结构,或配合其他算法。
参考资料
示例用于理解所注明的运行环境与边界;延伸学习可结合原文中的更多案例。