深蓝黑背景封面:右侧大标题「滑动窗口三类题,一套模板通吃」,副标题「定长 · 变长最值 · 至多 K 约束」;左侧示意图为三行各 8 格的数组:第一行高亮中间 3 格并配括线标注「长度恒为 k」,表示定长窗口;第二行高亮中间 5 格,下方标注「左端可收缩、右端可扩张」,表示变长最值窗口;第三行高亮前 7 格,其中两格画有紫色叉号,标注「违规数 2 ≤ K」,表示至多 K 个约束的窗口;左下角一行通用骨架「右扩 → 更新统计 → 违规则左缩 → 更新答案」;左上标注「知识延伸 · 算法」,右上圆角胶囊标注「Day 04 · 11-11」 图 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²) 枚举区间的本质改进——每个元素最多进窗口一次、出窗口一次。

深蓝黑背景概念图,标题「三类窗口,同一副骨架」。左侧大卡片「通用循环」自上而下五步流程:第一步右指针 right 右移读入新元素;第二步更新窗口统计(长度、求和或计数);第三步 while 违反不变量时左指针 left 右移收缩;第四步窗口合法则用当前窗口更新答案;第五步 right 越界结束、否则回到第一步,步骤之间用青色箭头连接。右侧三张横向卡片依次对照三类题型:定长窗口(不变量:窗口长度恒为 k,右进一格左必出一格;代表题:长度为 k 的子数组最大和、定长滑动平均);变长最值窗口(不变量:窗口内始终满足条件,如无重复字符;代表题:最长无重复子串、和达标的最短子数组);至多 K 约束窗口(不变量:窗口内违规元素数不超过 K;代表题:至多 K 个不同字符的最长子串、至多翻转 K 次的最长连续相同子串)。底部总结条:所有窗口题只回答两件事——什么时候扩右指针,什么时候缩左指针,由不变量决定 图 2:通用循环五步与三类题型不变量的对照。

两个高频翻车点。

一是收缩条件写成 if 而不是 while:当一次违规需要移出多个元素才能恢复不变量时(比如「和不超过 target」的窗口,新元素很大时要连出好几格),if 只缩一格就放行了,答案悄悄偏大。二是把「至多 K」读成「恰好 K」:不变量永远是「不超过 K」,「恰好 K 个不同字符的最长子串」正确做法是维护至多 K 的窗口、在计数恰好等于 K 时刷新答案,而不是让窗口恒等于 K。

拿到任何一道窗口题,先问自己两件事:右指针什么时候扩(永远是每一步都扩)、左指针什么时候缩(不变量被破坏时)。不变量想清楚,代码就是骨架的填空。你最近遇到的窗口题属于这三类里的哪一类,不变量又是什么?欢迎在评论区对号入座。