sko.kr

算法 - 1. 滑动窗口（固定大小）

algorithmssliding-windowarraysoptimizationtwo-pointers
By sko•9/27/2025•7 min read

何时使用固定大小滑动窗口

当你需要找到特定大小的最优连续子数组时，使用固定大小滑动窗口。虽然大小约束看起来有限，但这种模式经常出现：

  • 最大/最小和 k个连续元素的（经典用例）
  • 平均值 k个连续元素的
  • 模式匹配 使用固定长度模式（如查找字母异位词）
  • 滚动哈希 用于子串匹配
  • 时间序列分析 使用固定时间窗口（例如：7天移动平均）
  • 任何需要分析所有大小为k的子数组的问题

示例问题

K个元素的最大和：给定每日销售收入 [100, 200, 300, 400, 100, 200, 50]，找到总收入最高的3连续天期间。

  • 天[0-2]：100 + 200 + 300 = 600
  • 天[1-3]：200 + 300 + 400 = 900 ✓ 最佳期间
  • 天[2-4]：300 + 400 + 100 = 800
  • 天[3-5]：400 + 100 + 200 = 700
  • 天[4-6]：100 + 200 + 50 = 350

答案：第1-3天拥有最高总收入$900。

最重要的洞察

重用重叠计算 - 大小为k的相邻窗口共享k-1个公共元素，仅在一个退出的元素和一个进入的元素上有所不同，因此我们只需更新这两个变化而不是重新计算一切，从而实现O(n)而非O(n*k)的复杂度。

备注：这个算法的天才之处在于认识到相邻窗口显著重叠。对于大小为3的窗口，向前移动意味着2个元素保持相同 - 只有最左边的退出，新的最右边的进入。我们维护运行状态并递增更新，而不是从头重新计算。一次减法，一次加法 - 这就是"滑动"到下一个窗口所需的全部。

决策框架

在窗口的每次滑动中，你执行两个操作：

  • 移除退出窗口的元素的贡献（左侧）
  • 添加进入窗口的元素的贡献（右侧）

代码

// 注意：我们使用for循环（不是while）因为：
// - 在固定大小滑动窗口中，我们恰好处理每个元素一次
// - 右指针总是递增1
// - for循环更清洁且防止忘记right++

// 恰好大小为k的固定窗口
// 我们需要检查每个可能的k大小窗口
function maxSumOfK(nums: number[], k: number): number {
  if (nums.length < k) return -1;

  let windowSum = 0;
  let maxSum = -Infinity;
  let left = 0;

  for (let right = 0; right < nums.length; right++) {
    // 将当前元素添加到窗口
    const elementEnteringWindow = nums[right];
    windowSum += elementEnteringWindow;

    // 决策框架：维护恰好大小为k的窗口
    const windowSize = right - left + 1;
    // 当窗口恰好为k时处理，然后滑动它
    if (windowSize === k) {
      maxSum = Math.max(maxSum, windowSum);
      // 为下次迭代滑动窗口
      const elementLeavingWindow = nums[left];
      windowSum -= elementLeavingWindow;
      left++;
    }
  }

  return maxSum;
}

// 最多大小为k的窗口
// "k距离内的重复"意味着我们需要一个永不超过k的窗口
function hasDuplicateWithinK(nums: number[], k: number): boolean {
  const window = new Set<number>();
  let left = 0;

  for (let right = 0; right < nums.length; right++) {
    // 决策框架：维护窗口大小 <= k
    // 为什么与上面不同？"k距离内"意味着最多相距k个元素
    // 所以我们维护一个增长到k的固定窗口，然后在大小k时滑动
    const windowSize = right - left + 1;
    const windowExceedsK = windowSize > k;
    if (windowExceedsK) {
      const elementLeavingWindow = nums[left];
      window.delete(elementLeavingWindow);
      left++;
    }

    // 检查当前窗口中的重复
    const currentElement = nums[right];
    const isDuplicate = window.has(currentElement);

    if (isDuplicate) {
      return true;
    }

    // 将当前元素添加到窗口
    window.add(currentElement);
  }

  return false;
}

疑问解答

常见疑问："为什么要追踪窗口和？我不能使用嵌套循环分别对每个k元素窗口求和吗？"

为什么你可能认为嵌套循环就够了

考虑在 [100, 200, 300, 400, 100, 200, 50] 中用k=3找最大和：

  • "我可以用外层循环表示起始位置，内层循环对k个元素求和"
  • "对于每个起始位置i，从i到i+k-1求和"
  • "只有3个元素，所以内层循环很小"
  • "代码更直观 - 我可以准确看到什么被求和了"

为什么这种想法是低效的

关键认识：嵌套循环重复重新计算相同的元素！

让我们用k=3追踪 [100, 200, 300, 400, 100, 200, 50]：

嵌套循环方法（O(n*k)）：
窗口[0-2]：100 + 200 + 300 = 600    （3次加法）
窗口[1-3]：200 + 300 + 400 = 900    （3次加法）
窗口[2-4]：300 + 400 + 100 = 800    （3次加法）
窗口[3-5]：400 + 100 + 200 = 700    （3次加法）
窗口[4-6]：100 + 200 + 50 = 350     （3次加法）
总计：15次加法

滑动窗口（O(n)）：
初始[0-2]：100 + 200 + 300 = 600   （3次加法）
滑动到[1-3]：600 - 100 + 400 = 900  （1次减法，1次加法）
滑动到[2-4]：900 - 200 + 100 = 800  （1次减法，1次加法）
滑动到[3-5]：800 - 300 + 200 = 700  （1次减法，1次加法）
滑动到[4-6]：700 - 400 + 50 = 350   （1次减法，1次加法）
总计：3次加法 + 4次减法 + 4次加法 = 11次操作

注意像300这样的元素在嵌套循环中被加了3次，但在滑动窗口中只加了一次！

具体例子：扩展问题

对于在10,000个元素的数组中用k=1000找最大和：

嵌套循环：

  • 每个窗口：对1000个元素求和
  • 总窗口数：9001
  • 总加法次数：9,001,000

滑动窗口：

  • 初始窗口：1000次加法
  • 每次滑动：1次减法 + 1次加法
  • 总操作数：1000 + (9000 × 2) = 19,000
  • 快474倍！

为什么优化很重要

滑动窗口技术：

  • 重用重叠计算（k-1个元素保持相同）
  • 每个元素恰好被加一次，恰好被减一次
  • 没有相同元素的冗余计算
  • 将O(n×k)嵌套循环解法转换为O(n)滑动窗口

关键洞察：当移动窗口一个位置时，只有2个元素改变（一个离开，一个进入），那为什么要重新计算一切呢？

← Back to Blog