滑动窗口专题

滑动窗口解决的是「连续区间」的最值 / 计数问题。它的价值是把 O(n²) 的枚举压成 O(n)——每个元素最多进窗口一次、出窗口一次，所以整体线性。

一、右扩左缩的循环

四步循环：右指针扩张把新元素纳入窗口 → 更新窗口内状态（计数、求和）→ 满足条件时收缩左指针并同步更新状态 → 记录答案。写成框架后，所有滑动窗口题的区别只在「状态是什么」和「收缩条件是什么」。

关键在于：右指针一路向右不回头，左指针只在「不得不缩」时才动。所以每个元素进出窗口各一次，总步数是 2n 量级，复杂度 O(n)。这也是它优于「枚举所有起点终点」双层循环的根本原因。

let left = 0
for (let right = 0; right < n; right++) {
  window.add(s[right])          // 加入窗口，更新 count / sum
  while (窗口需要收缩) {
    window.remove(s[left])       // 移除左端，left++
    left++
  }
  更新答案(window)              // 当前窗口满足条件时记录
}

写成框架后题型就统一了，差别只在状态与收缩条件

图：右扩找可行、左缩求最优，两个指针都只向右走

二、定长与不定长

固定长度：窗口大小恒定，右移即出即进，常用于「长度为 k 的最大/最小」。
可变长度：由约束条件决定何时收缩，常用于「最长无重复」「最短覆盖」。

// 固定长度 k：右移一格，左端出、右端进
for (let right = 0; right < n; right++) {
  window.add(s[right])
  if (right >= k) window.remove(s[right - k])
  if (right >= k - 1) 更新答案(window)  // 窗口刚好填满 k 个才开始记答案
}

先判断窗口大小是否固定，决定用哪套模板，别混用。固定长度窗口常用于「滑动最大值」类单调队列题，但它和双端队列是两回事——纯固定窗口不需要单调队列，只有「窗口内最大值」才需要。

三、窗口内的状态量

计数用数组或 Map，求和用一个累加变量。关键是收缩时要正确回退状态——左指针移出元素时，把它的计数减一、把它从求和里扣掉，否则窗口状态是假的。求和类尤其容易漏回退：左指针移出 s[left] 时，sum -= s[left] 必须跟着做，否则窗口和会越加越大，收缩条件永远不成立，指针卡死。

最容易写错的是「判断是否满足条件」这一步。比如最小覆盖子串，若每次都遍历整个 need map 看是否覆盖，判断就是 O(m)。用 valid 计数技巧：维护一个计数器，某字符在窗口内的数量刚达到目标数量时 valid++，刚低于时 valid--；valid === need.size 即覆盖。这样判断变成 O(1)。

// valid 技巧：满足条件时 valid 自增，只在 O(1) 内判断覆盖
let valid = 0
window.set(c, (window.get(c) || 0) + 1)
if (window.get(c) === need.get(c)) valid++
// 收缩时
if (window.get(c) === need.get(c)) valid-- // 即将低于目标，valid 减一
window.set(c, window.get(c) - 1)
if (valid === need.size) { /* 已覆盖，可收缩 */ }

别每次遍历整个 map 判断，用 valid 把判断降到 O(1)

四、三类经典题型

三道足够覆盖套路：

最长无重复子串：状态是字符计数，收缩条件是「出现重复」（某字符计数 > 1）。关键一行：if (count[s[right]] > 1) 收缩左端。
最小覆盖子串：状态是目标字符的满足情况，用上面的 valid 计数。关键一行：while (valid === need.size) 收缩并记录最短。
长度最小的子数组：状态是和，收缩条件是「和已达标」。关键一行：while (sum >= target) 收缩并记录最短。

第二道的 valid 技巧是核心——它把「是否覆盖」从 O(m) 降到 O(1)，避免内层再套一层遍历。

能不能用窗口，取决于条件随右指针移动是否单调：

// 元素全为正、条件为「和 <= k」：右移只会让和变大 → 单调，窗口可用

// 一旦含负数，右移后和可能变小 → 不再单调，左右指针推不动
// 这时换前缀和 + 哈希表
const prefix = [0]
const seen = new Map([[0, 1]])
let count = 0
for (const n of nums) {
  const cur = prefix.at(-1) + n
  count += seen.get(cur - k) ?? 0
  seen.set(cur, (seen.get(cur) ?? 0) + 1)
  prefix.push(cur)
}

五、和前缀和的区别

滑动窗口适合「连续区间 + 单调可收缩」。一旦条件失去单调性（比如数组含负数，区间和不再随长度单调变化），左右指针的单调推进就不成立，该换前缀和 + 哈希表。例如「区间和等于 k」：正数时窗口可收缩，含负数时收缩可能漏解，正确做法是用前缀和 pre[i] - pre[j] === k 配合哈希表查 pre[i] - k。

// 区间和等于 k（可能含负数）：前缀和 + 哈希表，而非滑动窗口
const pre = new Map([[0, 1]])
let sum = 0, ans = 0
for (const x of nums) {
  sum += x
  ans += pre.get(sum - k) || 0 // 找之前出现过 sum-k 的位置
  pre.set(sum, (pre.get(sum) || 0) + 1)
}

存在负数或条件非单调时，左右指针推不动，换前缀和

六、窗口不只用来求最值

滑动窗口不只适用于子串问题，它适用于任何「连续区间 + 单调可收缩」的场景。

存在负数或条件非单调时它也用不了——左右指针的单调推进不成立，这时要换前缀和。

状态只用 Map 同样不够：每次遍历整个 map 判断是否满足条件会让复杂度退化，需要额外的满足计数（valid）把判断降到 O(1)。

写成框架之后题型就统一了，差别只在状态与收缩条件。

OI Wiki 滑动窗口把窗口的收缩条件拆得很清楚，卡在「什么时候缩」时可以看。

一、右扩左缩的循环​

二、定长与不定长​

三、窗口内的状态量​

四、三类经典题型​

五、和前缀和的区别​