滑动窗口 - 算法与数据结构教程

讲解

滑动窗口解决的是「连续子数组 / 子串满足某性质」的一类问题：最长无重复字符子串、长度最小的达标子数组、定长窗口的最值。如果用暴力法枚举所有起点终点再检查，是 O(n²) 甚至 O(n³)；滑动窗口的洞察是：当右端点右移时，左端点不需要回退——它只会单调右移。两个端点各自最多走 n 步，总复杂度 O(n)。

窗口的标准写法是双指针加一份「窗口内状态」：右指针负责扩张（纳入新元素、更新状态），当窗口违反约束时，左指针负责收缩（移出旧元素、回滚状态），每一步顺手更新答案。状态的载体因题而异：计数 Map、出现次数数组、当前和、单调队列（单调队列一章专门讲）。写滑动窗口代码，把「扩张—收缩—更新答案」三段式写清楚，逻辑就不会乱。

什么情况下左指针单调右移成立？关键是约束的「单调性」：窗口扩大只会朝着某个方向改变达标状态（如子数组和只在元素非负时单调增）。遇到含负数的子数组和类问题，滑动窗口会失效，要换前缀和 + 哈希表（前缀和一章会讲）——能识别模式的适用边界，比会默写模板重要。

示例

两道代表作。无重复字符的最长子串：用 Map 记录每个字符上次出现的位置，左指针直接跳到重复字符之后；长度最小的子数组（元素均为正数）：右指针累加，和达标后左指针尽量收缩：

import assert from 'node:assert/strict';

function lengthOfLongestSubstring(s) {
  const lastSeen = new Map(); // 字符 -> 最近下标
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {
      left = lastSeen.get(ch) + 1; // 左指针跳过重复字符
    }
    lastSeen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

function 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 best === Infinity ? 0 : best;
}

assert.strictEqual(lengthOfLongestSubstring('abcabcbb'), 3);
assert.strictEqual(lengthOfLongestSubstring('bbbbb'), 1);
assert.strictEqual(lengthOfLongestSubstring('pwwkew'), 3);
assert.strictEqual(lengthOfLongestSubstring(''), 0);

assert.strictEqual(minSubArrayLen(7, [2, 3, 1, 2, 4, 3]), 2);
assert.strictEqual(minSubArrayLen(4, [1, 4, 4]), 1);
assert.strictEqual(minSubArrayLen(11, [1, 1, 1, 1, 1, 1, 1, 1]), 0);

console.log('滑动窗口示例全部通过');

对照看两个收缩循环的差异：第一题左指针「跳」到重复字符之后（借助 Map 一步到位），第二题左指针「爬」到刚好不达标为止（while 循环逐步收缩）。形态不同，骨架相同：右进左出、状态随行、每步更新答案。

常见坑

用 while 还是 if 收缩：约束可能被一次扩张多次违反时用 while 循环收缩；能保证最多违反一次时才可用 if，拿不准一律 while。
忘记更新窗口状态：左指针移出元素时必须同步回滚计数/和，漏掉这步答案全错且难以察觉。
lastSeen 没和 left 比较：重复字符若已在窗口之外（下标 < left），不应触发左移，示例里的 lastSeen.get(ch) >= left 判断就是防这个。
对含负数的数组用滑动窗口求和：元素有正有负时右移右端点和不再单调，该换前缀和 + 哈希。
答案初始化与「无解」语义：best 初始 Infinity、最后返回 0 表示无解——题目语义不同写法不同，先把「没有合法窗口时返回什么」定下来。

小结

滑动窗口 = 左右指针单调右移 + 窗口状态随进出更新，把连续子串/子数组问题压到 O(n)；先确认约束的单调性再用它。下一章看平均 O(1) 的查找利器：哈希表。