图 1:本文封面,三类窗口形态与同一副通用骨架。
同批的真题复盘讲了「至多翻转 m 次求最长连续相同子串」这一道题的完整推导;这篇我们把镜头拉远,看滑动窗口这个题型的完整谱系:定长、变长最值、至多 K 个约束,三类看起来毫不相干的题,其实共用同一副骨架。
先把骨架立起来:右扩、更新、收缩、记录。
所有滑动窗口题都在维护「一个区间 + 一条不变量」:窗口必须始终满足的条件。通用循环只有五步——右指针 right 右移读入新元素;更新窗口统计(长度、求和或计数);当不变量被破坏时左指针 left 右移收缩;窗口合法则用当前窗口更新答案;right 越界则结束。写成代码骨架是:
let left = 0;
for (let right = 0; right < arr.length; right++) {
读入 arr[right],更新窗口统计;
while (不变量被破坏) {
移出 arr[left],left++;
}
用当前窗口 [left, right] 更新答案;
}
三类题的差别,只在「不变量是什么」这一件事上。
第一类:定长窗口,不变量是「窗口长度恒为 k」。
右端每进一格,左端就必须出一格,窗口像一截固定长度的车厢滑过数组。代表题是「长度为 k 的子数组最大和」与「定长滑动平均」。由于窗口长度固定,收缩条件可以直接写成「下标超过 k 就出一格」,连 while 都省了:
function maxSumFixedK(arr, k) {
let sum = 0, best = -Infinity;
for (let right = 0; right < arr.length; right++) {
sum += arr[right]; // 右扩
if (right >= k) sum -= arr[right - k]; // 长度超 k,左端出一格
if (right >= k - 1) best = Math.max(best, sum);
}
return best;
}
第二类:变长最值窗口,不变量是「窗口内始终满足某条件」。
典型是「最长无重复字符子串」:不变量是窗口内不允许重复字符。右端读到的字符若在窗口内已存在,左端直接跳到它上一次出现位置之后。这类题求的是「满足条件的最长(或最短)窗口」,窗口长度本身不固定,答案在每次窗口合法时刷新。
求「最短」时模板有一个小动作要变:答案不在收缩之后刷新,而在收缩循环内部刷新——每缩一格都得到一个仍然达标但更短的窗口,比如「和不小于 target 的最短子数组」,每次 while 里 sum 仍达标时就尝试更新答案。同一个骨架,只是答案刷新的时机跟着「最长/最短」换边。
第三类:至多 K 个约束,不变量是「窗口内违规元素数不超过 K」。
代表题是「至多 K 个不同字符的最长子串」,同批真题那道「至多翻转 m 次」也属于这一类——翻转次数就是一种违规计数,窗口内待翻转字符数不超过 m。以 K 个不同字符为例:
function longestAtMostKDistinct(s, k) {
const cnt = new Map();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
cnt.set(s[right], (cnt.get(s[right]) ?? 0) + 1);
while (cnt.size > k) { // 不同字符数超 K,收缩
cnt.set(s[left], cnt.get(s[left]) - 1);
if (cnt.get(s[left]) === 0) cnt.delete(s[left]);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
这三段代码用 Node.js 22 实际运行并对拍验证:定长窗口 [2,1,5,1,3,2]、k=3 输出 9;无重复子串 abcabcbb 输出 3;K=2 时 eceba 输出 3;再各跑两万组随机小数据与暴力枚举逐一比对,不一致数为零。
为什么这套骨架是线性的。
关键在于两个指针都只进不退:right 走 n 步,left 全程也最多走 n 步,while 循环看起来嵌套,总执行次数却被 left 的移动次数封顶,整体就是 O(n)。这也是窗口法相对 O(n²) 枚举区间的本质改进——每个元素最多进窗口一次、出窗口一次。
图 2:通用循环五步与三类题型不变量的对照。
两个高频翻车点。
一是收缩条件写成 if 而不是 while:当一次违规需要移出多个元素才能恢复不变量时(比如「和不超过 target」的窗口,新元素很大时要连出好几格),if 只缩一格就放行了,答案悄悄偏大。二是把「至多 K」读成「恰好 K」:不变量永远是「不超过 K」,「恰好 K 个不同字符的最长子串」正确做法是维护至多 K 的窗口、在计数恰好等于 K 时刷新答案,而不是让窗口恒等于 K。
拿到任何一道窗口题,先问自己两件事:右指针什么时候扩(永远是每一步都扩)、左指针什么时候缩(不变量被破坏时)。不变量想清楚,代码就是骨架的填空。你最近遇到的窗口题属于这三类里的哪一类,不变量又是什么?欢迎在评论区对号入座。