sko.kr

算法 - 2. 滑动窗口（可变大小）

algorithmssliding-windowtwo-pointersoptimizationarraysstrings
By sko•9/28/2025•10 min read

何时使用可变大小滑动窗口

当你需要找到大小未预先确定的最优连续子数组时，使用可变大小滑动窗口。该算法动态调整窗口边界，在优化大小的同时保持特定条件。

  • 总和 ≥ 目标值的最小/最大子数组（经典用例）
  • 没有重复字符的最长子字符串
  • 包含所有必需字符的最小窗口子字符串
  • 具有特定属性的子数组数量
  • 有种类约束的最大物品收集（例如：水果篮）
  • 任何窗口大小需要适应以保持条件的问题

示例问题

最小购物袋：给定物品重量 [2, 3, 1, 2, 4, 3]，需要至少7公斤的总重，要选择的连续物品的最小数量是多少？

  • 物品 [0-3]：2 + 3 + 1 + 2 = 8 kg ✓（4个物品）
  • 物品 [1-4]：3 + 1 + 2 + 4 = 10 kg ✓（4个物品）
  • 物品 [2-4]：1 + 2 + 4 = 7 kg ✓（3个物品）
  • 物品 [4-5]：4 + 3 = 7 kg ✓（2个物品）← 最佳！

答案：2个物品（位置4-5的物品）。

最重要的洞察

扩展窗口以探索可能性，然后在满足条件时从左侧收缩 - 这种扩展-收缩的舞蹈通过系统地调整边界来找到最优大小，保证我们检查所有有效窗口，而无需检查所有O(n²)个可能性。

心理笔记：该算法的天才之处在于维护一个"有效窗口不变式"。在每一步，我们只需要决定："我能收缩这个窗口并仍然满足条件吗？"这个简单的决定自动找到最优窗口。我们不是检查所有可能的窗口，而是扩展以包含新元素，然后贪婪地收缩以找到在每个位置结束的最小有效窗口。

决策框架

在每个位置，算法做出两个连续的决定：

  • 扩展：始终包含当前元素（移动右指针）
  • 收缩：当条件满足时，尝试通过从左侧移除来最小化

代码

// 找到总和 >= 目标值的最小大小子数组
// 尽管有嵌套循环，但时间复杂度O(n) - 每个元素最多访问两次
function shortestSubarray(nums, target) {
  let left = 0;
  let windowSum = 0;
  let minLength = Infinity;

  for (let right = 0; right < nums.length; right++) {
    // 步骤1：扩展 - 始终包含当前元素
    const elementEnteringWindow = nums[right];
    windowSum += elementEnteringWindow;

    // 决策框架：我们能收缩并仍然满足条件吗？
    // 使用while（而不是if）来找到最优窗口，而不仅仅是任何有效窗口
    while (windowSum >= target) {
      // 当前窗口满足条件，如果是最小的则记录
      const currentWindowSize = right - left + 1;
      minLength = Math.min(minLength, currentWindowSize);

      // 尝试通过从左侧收缩找到更小的有效窗口
      const elementLeavingWindow = nums[left];
      windowSum -= elementLeavingWindow;
      left++;
    }
  }

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

// 最多k个不同字符的最长子字符串
// 问题：找到最多包含k个不同字符的最长子字符串
// 例子：k=2的"eceaba" → "eceab"有3个字符 ✗，"eceba"有3个字符 ✗，"ece"有2个字符 ✓
function longestSubstringKDistinct(s, k) {
  const charFrequency = new Map(); // 跟踪窗口中每个字符的数量
  let left = 0;
  let maxLength = 0;

  for (let right = 0; right < s.length; right++) {
    // 扩展：向窗口添加字符
    const charEntering = s[right];
    charFrequency.set(charEntering, (charFrequency.get(charEntering) || 0) + 1);

    // 决策框架：如果超过k个不同字符，从左侧收缩
    // 为什么从左侧收缩，而不是右侧？因为：
    // 1. 我们系统地尝试每个位置作为右边界
    // 2. 对于每个右位置，我们找到最左边的有效位置
    // 3. 这确保我们检查所有可能的窗口（见下面的疑惑消除）
    while (charFrequency.size > k) {
      const charLeaving = s[left];
      const count = charFrequency.get(charLeaving);

      // 减少离开窗口的字符的频率
      if (count === 1) {
        // 这是最后一次出现，从映射中删除
        charFrequency.delete(charLeaving);
      } else {
        // 窗口中仍有更多出现
        charFrequency.set(charLeaving, count - 1);
      }
      left++;
    }

    // 这里窗口是有效的（≤ k个不同字符），更新最大值
    const currentWindowSize = right - left + 1;
    maxLength = Math.max(maxLength, currentWindowSize);
  }

  return maxLength;
}

疑惑消除

常见疑惑："为什么只从左侧收缩？如果从右侧移除会得到更好的结果怎么办？"

为什么你可能认为从右侧移除可能更好

这是一个自然的担忧！当窗口有太多不同的字符时，你可能会想：

  • "我们刚刚添加的字符（在右侧）是问题吗？"
  • "也许从右侧移除会保持更长的有效窗口？"
  • "为什么不尝试两个方向并选择更好的一个？"
  • "总是从左侧收缩的贪婪选择似乎是任意的"

例如，对于字符串"abcba"和k=2：

  • 当我们到达索引2（字符'c'）时，窗口是有3个不同字符的"abc"
  • 从左侧移除得到"bc"（长度2）
  • 但如果从右侧移除得到"ab"（也是长度2）？
  • 我们不应该考虑两个选项吗？

为什么这种想法是错误的

关键认识：我们不需要从右侧移除，因为我们会在未来的迭代中自然地探索该选项！

这是关键的洞察：**算法系统地尝试每个位置作为右边界。**因此，如果从右侧移除会给出更好的窗口，我们会在到达该位置时发现它。

让我们用"abcba"和k=2来证明这一点：

right=0：窗口 ["a"]，1个不同字符，有效 ✓
right=1：窗口 ["ab"]，2个不同字符，有效 ✓，maxLen=2
right=2：窗口 ["abc"]，3个不同字符，无效 ✗
  - 从左侧收缩：["bc"]，2个不同字符，有效 ✓
right=3：窗口 ["bcb"]，2个不同字符，有效 ✓，maxLen=3
right=4：窗口 ["bcba"]，3个不同字符，无效 ✗
  - 收缩：["cba"]，3个不同字符，仍无效 ✗
  - 收缩：["ba"]，2个不同字符，有效 ✓

关键洞察：当我们有"abc"并从左侧移除得到"bc"时，你担心我们错过了"ab"。但请注意：

  • 窗口"ab"在right=1时已经被评估了！
  • 我们在那时记录了它的长度（2）
  • 后来，我们找到了长度为3的"bcb"，这更好

每个可能的窗口都被评估，因为：

  1. 在位置1结束的窗口：我们尝试了["a"]，["ab"]
  2. 在位置2结束的窗口：我们尝试了["abc"]→["bc"]，["c"]
  3. 在位置3结束的窗口：我们尝试了["bcb"]，["cb"]，["b"]
  4. 依此类推...

算法不会错过任何窗口 - 它系统地评估所有窗口！

具体证明：为什么从左侧收缩就足够了

这样想：如果有一个最优窗口[i, j]，算法将找到它：

  1. 当右指针到达j时：我们将拥有从某个左位置到j的所有元素
  2. while循环收缩：它将左指针向右移动，直到窗口有效
  3. 它将在i或之前停止：因为[i, j]是有效的，收缩将在位置i停止
  4. 我们记录这个窗口：如果它是迄今为止看到的最好的，我们更新最大值

为什么从右侧移除是多余的

想象我们在位置right=5，窗口[2,3,4,5]是无效的。你可能会想"如果[2,3,4]比[3,4,5]更好怎么办？"

但这是我们不需要检查[2,3,4]的原因：

  • 当right在位置4时，我们已经检查了[2,3,4]！
  • 如果[2,3,4]是有效且良好的，我们当时就记录了它
  • 现在在位置5，我们正在找到以5结束的最佳窗口
  • 下一次迭代（right=6），我们将找到以6结束的最佳窗口

算法的保证：对于数组中的每个可能的窗口，将有一个时刻：

  • 右指针在窗口的结束位置
  • 左指针将被移动到（或超过）窗口的开始位置
  • 因此，每个窗口恰好被评估一次

这就是为什么算法是O(n)而不是看起来需要的O(n²) - 我们永远不需要回溯或重新考虑以前的决定。

← Back to Blog