算法篇 ｜ 滑动窗口

前言

在上一章中，我们讲了双指针——通过两个指针的协作来高效处理”一对元素”的问题。这一章我们来聊滑动窗口（Sliding Window），它本质上是双指针的一个特化版本，专门用来解决连续子序列问题。

滑动窗口的核心思想可以用一句话概括：维护一个窗口（由左右两个指针界定），通过右指针扩大窗口、左指针缩小窗口的方式，在 O(n) 时间内找到满足条件的最优子序列。

为什么滑动窗口值得单独拿出来讲？因为它是前端面试中出现频率最高的算法题型之一。“无重复字符的最长子串”、“最小覆盖子串”这类题，几乎是大厂面试的标配。而且滑动窗口有一个非常好用的通用模板，一旦掌握，就能套用到各种变体题目上。

本章我们会讲解：固定窗口 vs 可变窗口的区别、通用模板代码、三道经典 LeetCode 题目，让你彻底吃透这个技巧。

诊断自测

Q1：给定字符串 "abcabcbb"，找出不含重复字符的最长子串的长度。你的思路是什么？

Q2：固定窗口和可变窗口的区别是什么？分别适用于什么场景？

一、固定窗口 vs 可变窗口

1.1 固定窗口

窗口大小是预先确定的（通常题目会给出 k），两个指针保持固定间距同步右移。

// 固定窗口模板
function fixedWindow(arr, k) {
  // 先初始化第一个窗口
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }

  let maxSum = windowSum;

  // 窗口滑动：加入右边新元素，移出左边旧元素
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i];       // 新元素进入窗口
    windowSum -= arr[i - k];   // 旧元素离开窗口
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

固定窗口比较简单，面试中出现频率不高，我们重点讲可变窗口。

1.2 可变窗口

窗口大小可伸缩，这才是滑动窗口的精髓。根据目标不同，可变窗口又分为两种：

• 找最长：右指针尽量扩大窗口，只有当窗口不满足条件时才收缩左指针
• 找最短：右指针扩大窗口直到满足条件，然后尝试收缩左指针来寻找更短的答案

二、可变窗口通用模板

下面这个模板可以覆盖绝大多数可变窗口的题目：

function slidingWindow(s) {
  const window = new Map(); // 维护窗口内的状态
  let left = 0;
  let result = 初始值;

  for (let right = 0; right < s.length; right++) {
    // 1. 右指针元素进入窗口，更新窗口状态
    const charIn = s[right];
    // ... 更新 window ...

    // 2. 判断是否需要收缩窗口
    while (窗口需要收缩的条件) {
      // 3. 左指针元素离开窗口，更新窗口状态
      const charOut = s[left];
      // ... 更新 window ...
      left++;
    }

    // 4. 更新结果（根据题目要求，可能在收缩前/后/过程中更新）
    result = 更新逻辑;
  }

  return result;
}

模板的关键点：

1. 右指针只管往右走，不会回退——这保证了 O(n) 的时间复杂度
2. 左指针在内层循环中收缩，但它在整个过程中也只会从左走到右，总共最多移动 n 次
3. 窗口状态用 Map 或其他数据结构维护，保证进出窗口的操作都是 O(1)
4. 收缩条件和结果更新时机是每道题的差异点，也是需要思考的核心

三、经典题目

3.1 无重复字符的最长子串（LeetCode 3）

给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。

这是滑动窗口最经典的入门题。

思路：窗口内不能有重复字符。右指针扩大窗口时，如果新字符已经在窗口中了，就收缩左指针直到窗口中没有重复字符。

function lengthOfLongestSubstring(s) {
  const window = new Set();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    // 如果右指针的字符已经在窗口中，收缩左指针
    while (window.has(s[right])) {
      window.delete(s[left]);
      left++;
    }

    // 右指针字符进入窗口
    window.add(s[right]);

    // 更新结果
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

还有一种用 Map 的优化写法，可以直接跳过中间的字符：

function lengthOfLongestSubstring(s) {
  const map = new Map(); // 记录每个字符最后出现的位置
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    if (map.has(s[right]) && map.get(s[right]) >= left) {
      // 直接跳到重复字符的下一个位置
      left = map.get(s[right]) + 1;
    }

    map.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

复杂度分析：

• 时间复杂度：O(n)，每个字符最多被访问两次（进窗口一次，出窗口一次）
• 空间复杂度：O(min(n, m))，m 是字符集大小

3.2 长度最小的子数组（LeetCode 209）

给定一个正整数数组 nums 和一个正整数 target，找出满足和 >= target 的最短连续子数组的长度。

这是”找最短”的典型题目。

思路：右指针扩大窗口累加元素，当窗口和 >= target 时，尝试收缩左指针来寻找更短的答案。

function minSubArrayLen(target, nums) {
  let left = 0;
  let sum = 0;
  let minLen = Infinity;

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

    // 窗口和满足条件时，尝试收缩
    while (sum >= target) {
      minLen = Math.min(minLen, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }

  return minLen === Infinity ? 0 : minLen;
}

注意：这道题之所以可以用滑动窗口，是因为数组元素都是正整数。正整数保证了窗口和的单调性——右指针右移和一定增大，左指针右移和一定减小。如果数组包含负数，滑动窗口就失效了（参见前缀和那章的误区四）。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

3.3 最小覆盖子串（LeetCode 76）

给定字符串 s 和 t，在 s 中找出包含 t 所有字符的最短子串。

这是滑动窗口的”终极 Boss”题目，面试中出现频率非常高，难度也最大。

思路：

1. 先用一个 Map 统计 t 中每个字符需要的个数
2. 右指针扩大窗口，每次新字符进入时更新”已满足的字符数”
3. 当所有字符都满足时，尝试收缩左指针，找更短的答案
4. 在收缩过程中更新最优解

function minWindow(s, t) {
  // need：t 中每个字符需要的个数
  const need = new Map();
  for (const c of t) {
    need.set(c, (need.get(c) || 0) + 1);
  }

  // window：当前窗口中各字符的个数
  const window = new Map();
  let left = 0;
  let valid = 0; // 已满足条件的字符种类数
  let start = 0; // 最优子串的起始位置
  let minLen = Infinity;

  for (let right = 0; right < s.length; right++) {
    const charIn = s[right];

    // 右指针字符进入窗口
    if (need.has(charIn)) {
      window.set(charIn, (window.get(charIn) || 0) + 1);
      if (window.get(charIn) === need.get(charIn)) {
        valid++;
      }
    }

    // 所有字符都满足时，尝试收缩窗口
    while (valid === need.size) {
      // 更新最优解
      if (right - left + 1 < minLen) {
        start = left;
        minLen = right - left + 1;
      }

      const charOut = s[left];
      left++;

      // 左指针字符离开窗口
      if (need.has(charOut)) {
        if (window.get(charOut) === need.get(charOut)) {
          valid--;
        }
        window.set(charOut, window.get(charOut) - 1);
      }
    }
  }

  return minLen === Infinity ? '' : s.substring(start, start + minLen);
}

代码解读：

• need 记录目标字符串 t 中每个字符需要出现的次数
• window 记录当前窗口中每个字符的个数
• valid 记录当前窗口中已经满足条件的字符种类数（不是字符个数）
• 当 valid === need.size 时，说明窗口已经包含了 t 的所有字符
• 进出窗口时，只有当某个字符的数量恰好达到或恰好不足时，才更新 valid

复杂度分析：

• 时间复杂度：O(n + m)，n 是 s 的长度，m 是 t 的长度
• 空间复杂度：O(m)

面试追问：为什么用 valid === need.size 而不是直接比较两个 Map？

答：直接比较两个 Map 需要遍历所有键值对，每次比较是 O(m)。而维护一个计数器 valid，每次只需要 O(1) 的判断。这是一个常见的优化技巧。

四、如何判断一道题是否适合滑动窗口？

1. 题目求的是连续子序列（子串/子数组） — 不是子序列（可以不连续）
2. 窗口的扩大和缩小有单调性 — 扩大窗口一定”更满足”或”更不满足”条件
3. 正整数数组的区间和 — 可以用滑动窗口
4. 含负数的数组 — 通常不能用滑动窗口，考虑前缀和

滑动窗口 vs 双指针 vs 前缀和的选择：

常见误区

误区一：“滑动窗口的内层 while 循环使得时间复杂度变成 O(n²)”

这是最常见的误解。虽然代码里有两层循环，但左指针在整个过程中只从左到右移动了一次，总共最多移动 n 步。所以内层循环的总执行次数是 O(n)，而不是每次外层循环都执行 O(n) 次。总时间复杂度仍然是 O(n)。

一个好的理解方式是：每个元素最多进入窗口一次、离开窗口一次，所以总操作次数是 2n。

误区二：“滑动窗口只能用在字符串题上”

虽然最经典的几道题都是字符串题，但滑动窗口在数组中同样适用。“长度最小的子数组”、“乘积小于 K 的子数组”（LeetCode 713）、“最大连续 1 的个数 III”（LeetCode 1004）都是数组上的滑动窗口题。

误区三：“窗口收缩的条件一定是 while”

大多数”找最短”的题用 while 收缩（只要条件满足就一直缩），但”找最长”的题有时候用 if 就够了（只缩一步，保持窗口不会太大）。具体用 while 还是 if，取决于你是要找所有满足条件的最优解，还是只需要保证窗口状态合法。

误区四：“含负数的数组也可以用滑动窗口求子数组和”

不行。滑动窗口依赖一个关键假设：右指针右移使窗口”更接近满足条件”，左指针右移使窗口”更接近不满足条件”（或反过来）。负数的存在会打破这种单调性。比如 sum < target 时右指针右移，如果下一个元素是负数，sum 反而变小了，窗口收缩的逻辑就失效了。

小结

滑动窗口是双指针的一种特化形式，专门解决连续子序列问题。它的核心价值在于：右指针只往右走、左指针也只往右走，保证每个元素最多被处理两次，从而将暴力的 O(n²) 优化到 O(n)。

核心要点

1. 固定窗口：两个指针保持固定间距同步移动，适用于”大小为 k”的子数组问题
2. 可变窗口：右指针扩大、左指针收缩，适用于”最长/最短满足条件”的子序列问题
3. 通用模板：for 循环驱动右指针，while 循环收缩左指针，Map 维护窗口状态
4. 适用前提：窗口的扩大/缩小有单调性（正整数和、字符出现次数等）
5. 与前缀和的区别：含负数的子数组和问题用前缀和，不用滑动窗口

本章思维导图

练习挑战

第一题 ⭐：大小为 K 的子数组的最大平均值（LeetCode 643）

给定一个数组 nums 和一个整数 k，找出长度为 k 的子数组中的最大平均值。

// 示例
// 输入: nums = [1, 12, -5, -6, 50, 3], k = 4
// 输出: 12.75（子数组 [12, -5, -6, 50] 的平均值）

function findMaxAverage(nums, k) {
  // 初始化第一个窗口
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }

  let maxSum = windowSum;

  // 滑动窗口
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum / k;
}

第二题 ⭐⭐：字符串的排列（LeetCode 567）

给定字符串 s1 和 s2，判断 s2 是否包含 s1 的排列（即 s2 中是否存在一个子串是 s1 的某种排列）。

// 示例
// 输入: s1 = "ab", s2 = "eidbaooo"
// 输出: true（s2 包含 s1 的排列 "ba"）

function checkInclusion(s1, s2) {
  const need = new Map();
  for (const c of s1) {
    need.set(c, (need.get(c) || 0) + 1);
  }

  const window = new Map();
  let left = 0;
  let valid = 0;

  for (let right = 0; right < s2.length; right++) {
    const charIn = s2[right];
    if (need.has(charIn)) {
      window.set(charIn, (window.get(charIn) || 0) + 1);
      if (window.get(charIn) === need.get(charIn)) {
        valid++;
      }
    }

    // 窗口大小超过 s1 长度时，收缩左边
    while (right - left + 1 > s1.length) {
      const charOut = s2[left];
      left++;
      if (need.has(charOut)) {
        if (window.get(charOut) === need.get(charOut)) {
          valid--;
        }
        window.set(charOut, window.get(charOut) - 1);
      }
    }

    // 窗口大小恰好等于 s1 长度且所有字符都匹配
    if (valid === need.size) {
      return true;
    }
  }

  return false;
}

第三题 ⭐⭐⭐：最大连续 1 的个数 III（LeetCode 1004）

给定一个二进制数组 nums 和一个整数 k，最多可以翻转 k 个 0 为 1，返回最长的连续 1 的个数。

// 示例
// 输入: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
// 输出: 6（翻转下标 5 和 10 的 0）

function longestOnes(nums, k) {
  let left = 0;
  let zeroCount = 0;
  let maxLen = 0;

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

    // 窗口内 0 的个数超过 k 时，收缩左指针
    while (zeroCount > k) {
      if (nums[left] === 0) {
        zeroCount--;
      }
      left++;
    }

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

  return maxLen;
}

自我检测

• 能说清楚固定窗口和可变窗口的区别及各自的适用场景
• 能默写可变窗口的通用模板（for + while + Map）
• 能用滑动窗口解决”无重复字符的最长子串”
• 能解决”最小覆盖子串”，并解释 valid 计数器的作用
• 能解释为什么滑动窗口的时间复杂度是 O(n) 而不是 O(n²)
• 能判断一道题是否适合用滑动窗口（关键：连续子序列 + 单调性）
• 能区分什么时候用滑动窗口、什么时候用前缀和
• 能用滑动窗口解决”长度最小的子数组”，并解释为什么数组必须是正整数