双指针技巧

滑动窗口

什么时候想到它

看到题干里出现“连续的子串 / 子数组“，并且要你求最长、最短或者计数 —— 第一反应就该是滑动窗口。

它是双指针里快慢指针的一个特例： 两个指针同向走，中间夹着的那段就是“窗口”。右指针负责扩大窗口， 左指针负责收缩，一进一出，整个数组只走一遍，所以是 O(n)。

通用模板

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

  while (right < s.length) {
    const c = s[right];
    right++;                       // 扩大窗口
    // ... 把 c 加进窗口，更新窗口内的数据

    while (/* 窗口需要收缩 */) {
      const d = s[left];
      left++;                      // 缩小窗口
      // ... 把 d 移出窗口，更新窗口内的数据
    }
  }
}

⭐ 这个模板里真正需要你动脑的只有三处：

  1. 什么数据结构记录窗口内的状态（计数用 Map，求和用一个数字）
  2. 什么条件下需要收缩
  3. 答案在扩大之后更新，还是在收缩之后更新

其余的骨架一个字都不用改。认出题型 → 填这三个空，这就是模板化的意义。

例：最长无重复字符子串

题意复述：给一个字符串，找出其中不含重复字符的最长连续子串的长度。

function lengthOfLongestSubstring(s) {
  const window = new Map();
  let left = 0, res = 0;

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

    // 收缩条件：出现了重复字符
    while (window.get(c) > 1) {
      const d = s[left];
      left++;
      window.set(d, window.get(d) - 1);
    }

    res = Math.max(res, right - left + 1);
  }
  return res;
}

填的那三个空：Map 记字符计数、window.get(c) > 1 是收缩条件、 答案在收缩之后更新（因为收缩完窗口才重新合法）。

另一套写法：定长窗口

上面那套是变长窗口 —— 窗口大小由「收缩条件」决定。 还有一类题窗口是定长的（「每 k 个连续元素」），写法更简单，也不该套上面那个模板：

// 长度恰好为 k 的子数组里，和最大的是多少
function maxSumOfK(nums, k) {
  let sum = 0, best = -Infinity;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];                          // 进
    if (i >= k) sum -= nums[i - k];          // 🚨 出：窗口满了才开始扔
    if (i >= k - 1) best = Math.max(best, sum);   // 窗口刚好装满时才有答案
  }
  return best;
}

🚨 两个下标判断差一位，很容易写反：

  • i >= k 决定什么时候开始扔左边（第 k 个元素进来时，第 0 个该出去）
  • i >= k - 1 决定什么时候开始有答案（下标 k-1 时窗口刚装满 k 个）

⚠️ 把 i >= k - 1 写成 i >= k 会漏掉第一个窗口； 把 i >= k 写成 i > k 会让窗口多含一个元素、越滑越长。 两种错都不报错，只是答案偏了。

📌 判据很简单：题目里给了一个具体的窗口大小 → 定长； 说「最长/最短」→ 变长。 定长的不要用 while 收缩那套，写起来反而绕。

窗口里该维护什么

模板里的 window 是个占位。实际选什么，取决于收缩条件要问什么问题：

要判断的 维护什么
有没有重复字符 Map 计数（或 Set）
窗口内的和 一个数字，进出时加减
是否覆盖了目标串的全部字符 Map 计数 + 一个 valid 计数器
窗口内出现最多的字符有几个 Map 计数 + 一个最大值
窗口内的最大/最小值 ⭐ 单调队列 —— 普通结构做不到 O(1)

⭐ 最后一行值得单独记：「窗口内求最值」不能靠遍历窗口（那会退化成 O(nk)）， 要用单调队列。这是滑动窗口唯一一个「模板不够用」的场景。

🚨 有负数就不能用滑动窗口

这条限制在模板里看不出来，但它是滑窗最本质的前提：

窗口扩大时，那个「量」必须单调变化。

数组全是正数时，加一个元素和一定变大、减一个一定变小 —— 所以「太大就收缩」这个逻辑才成立。

有负数就断了：加一个元素可能让和变小，于是「现在太大了，收缩左边」这个判断 根本不成立 —— 也许再往右扩一个反而就合适了。

nums = [1, -1, 1, -1, 1],  求和恰好为 1 的子数组个数
  正确答案（暴力枚举）：6
  套滑动窗口：          3     ❌ 少了一半

⚠️ 滑窗漏掉的正是那些「中间和曾经超过 1、后来又降回来」的子数组 （比如整个 [1,-1,1,-1,1]）—— 它们在收缩那一步就被扔掉了，再也回不来。

⭐ 替代方案是前缀和 + 哈希表： 它不依赖单调性，代价是空间 O(n)。

📌 所以拿到「连续子数组」的题，第一件事是看有没有负数， 而不是直接套滑窗模板。

答案该在哪一步更新

这是滑动窗口最容易错的地方，而且错了往往只差一点点：

求什么 在哪更新答案
最长的合法窗口 收缩之后（此时窗口刚好合法）
最短的合法窗口 收缩之中（每收缩一次都检查一遍）

🚨 弄反了的症状是“答案总是差一”或者“大部分用例过、少数不过”， 看起来像边界问题，实际是这一步的位置错了。 调试时先确认这一条，比逐个用例去 print 快得多。

复杂度为什么是 O(n)

初看是两层循环，像 O(n²)。但左指针只会往前走，整个过程中最多走 n 步， 右指针同理。两个指针各自走一遍数组，加起来是 O(2n) = O(n)。

📌 这个“每个元素最多进出窗口各一次”的均摊分析， 是双指针类算法效率的共同来源，不只适用于滑动窗口。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。