【算法图解】滑动窗口：双指针的艺术

滑动窗口（Sliding Window）是很多题的“降维打击”：

本来要枚举所有子数组/子串：$O(n^2)$
用窗口维护一个区间：一趟扫描就搞定：$O(n)$

关键不在“双指针”，在窗口不变量：

你维护的窗口始终满足某个条件，一旦不满足就收缩。

1. 滑动窗口适用的典型条件

它适合“连续区间”的问题：

最长/最短满足条件的子串
统计满足条件的子数组数量
固定长度窗口的最大/最小值（常配单调队列）

不适合：

子序列（不连续）
需要全局组合枚举（通常是回溯/DP）

2. 通用模板：扩张右边界，必要时收缩左边界

function slidingWindow(s) {
  let left = 0
  const window = new Map()

  for (let right = 0; right < s.length; right++) {
    const ch = s[right]
    window.set(ch, (window.get(ch) ?? 0) + 1)

    while (/* 窗口不满足条件 */) {
      const d = s[left]
      window.set(d, window.get(d) - 1)
      if (window.get(d) === 0) window.delete(d)
      left++
    }

    // 此时窗口满足条件，可更新答案
  }
}

你要做的就是定义：

什么时候窗口满足
什么时候不满足

3. 例题：无重复字符的最长子串

目标：窗口内所有字符都不重复。

当加入新字符导致重复，就收缩左边界直到不重复。

function lengthOfLongestSubstring(s) {
  let left = 0
  let ans = 0
  const count = new Map()

  for (let right = 0; right < s.length; right++) {
    const ch = s[right]
    count.set(ch, (count.get(ch) ?? 0) + 1)

    while (count.get(ch) > 1) {
      const d = s[left]
      count.set(d, count.get(d) - 1)
      if (count.get(d) === 0) count.delete(d)
      left++
    }

    ans = Math.max(ans, right - left + 1)
  }

  return ans
}