07 · 滑动窗口

目标：默写「扩右缩左」框架。
精讲 3（完整）、76（可运行骨架）、209。

1. 为什么面试考

• 子串 / 子数组问题的一号套路，能把 O(n²) 降到 O(n)。
• 前端爱考：无重复最长子串（LeetCode 3）。
• 考你能不能维护窗口内的 状态（字符计数、和、覆盖情况）。

2. 零基础概念

滑动窗口 = 维护一段连续区间 [left, right]。

s = "abcabcbb"
      [---]        right 扩
        [---]      冲突 → left 缩
          [----]   再扩...

固定动作：

1. 扩：right++，把新元素纳入窗口，更新状态。
2. 缩：窗口不合法时，left++，移出左边元素，更新状态。
3. 记答案：在合法窗口上更新 max / min。

两种常见类型：

类型	特征	例子
可变窗口	扩到不合法再缩	3 无重复子串
求最短	合法时尽量缩 left	209、76

3. JS 模板（扩右缩左）

function slidingWindow(s, init, expand, shrink, update) {
  let left = 0
  let state = init()

  for (let right = 0; right < s.length; right++) {
    expand(state, s[right])

    while (shrink(state)) {
      update(state, left, right) // 可选：在缩之前记录
      // 移出 s[left]
      shrinkStep(state, s[left])
      left++
    }

    update(state, left, right)
  }

  return /* 答案 */
}

面试时不必拆这么细，记住 for 扩 right + while 缩 left 即可。

---

4. 精讲 · 3 无重复字符的最长子串

题意：求最长无重复子串长度。

状态：Set 或 Map 记录窗口内字符。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  const set = new Set()
  let left = 0
  let ans = 0

  for (let right = 0; right < s.length; right++) {
    while (set.has(s[right])) {
      set.delete(s[left])
      left++
    }
    set.add(s[right])
    ans = Math.max(ans, right - left + 1)
  }

  return ans
}

口述：

• right 每次纳入新字符。
• 若重复，left 一直缩，直到窗口内没有 s[right]。
• 合法后更新 ans = max(ans, 窗口长度)。

复杂度：每个字符最多进、出 Set 各一次 → O(n)。

---

5. 精讲 · 76 最小覆盖子串（可运行骨架）

题意：在 s 中找包含 t 全部字符的最短子串。

状态：

• need：t 中各字符需求量。
• window：当前窗口内各字符数量。
• formed：已满足需求量级的字符种类数；required = Object.keys(need).length。

套路：right 扩到 覆盖完整 → 记录答案 → left 尽量缩，仍保持覆盖。

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  if (t.length === 0 || s.length < t.length) return ''

  const need = {}
  for (const ch of t) {
    need[ch] = (need[ch] || 0) + 1
  }

  const window = {}
  let formed = 0
  const required = Object.keys(need).length

  let left = 0
  let ansLen = Infinity
  let ansStart = 0

  for (let right = 0; right < s.length; right++) {
    const c = s[right]
    window[c] = (window[c] || 0) + 1

    if (need[c] && window[c] === need[c]) {
      formed++
    }

    while (formed === required) {
      const len = right - left + 1
      if (len < ansLen) {
        ansLen = len
        ansStart = left
      }

      const leftChar = s[left]
      window[leftChar]--
      if (need[leftChar] && window[leftChar] < need[leftChar]) {
        formed--
      }
      left++
    }
  }

  return ansLen === Infinity ? '' : s.slice(ansStart, ansStart + ansLen)
}

关键逻辑：

步骤	做什么
扩 right	window[c]++；若 window[c] === need[c] → formed++
覆盖完整	formed === required 时尝试缩 left
缩 left	移出左字符；若某字符不再满足 → formed--，退出 while

先能跑通骨架，再记 formed 含义。

---

6. 精讲 · 209 长度最小的子数组

题意：正整数数组，和 ≥ target 的最短连续子数组长度。

套路：可变窗口 + 求最短——和够了就缩 left。

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
  let left = 0
  let sum = 0
  let ans = Infinity

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right]

    while (sum >= target) {
      ans = Math.min(ans, right - left + 1)
      sum -= nums[left]
      left++
    }
  }

  return ans === Infinity ? 0 : ans
}

对比 3 和 209：

题	扩	缩
3	默认扩	有重复才缩
209	默认扩	和 ≥ target 就缩（求最短）

---

7. 练习清单

题号	名称	难度	备注
3	无重复字符最长子串	Medium	本篇已精讲
209	长度最小的子数组	Medium	本篇已精讲
76	最小覆盖子串	Hard	本篇骨架
424	替换后的最长重复字符	Medium	窗口 + 字符计数
567	字符串排列	Medium	固定窗口长度

8. 今日验收

• [ ] 默写 3 的 while (set.has) { delete; left++ }
• [ ] 能说出 76 里 formed 和 required 的含义
• [ ] 默写 209：sum >= target 时更新 ans 并缩 left
• [ ] LeetCode 提交 3、209 至少各 1 次 AC；76 能跑通样例

9. 可选 · 记忆唤醒

for right 扩 → while 不合法/已够 缩 left
3：Set 判重，重复就缩
209：和够了就缩，记最短
76：need/window/formed，formed===required 时缩 left 试更短

下一步

→ 08 · 前缀和