数组中的滑动窗口 — 初学者的思维模型

Source: Dev.to

什么是滑动窗口？

滑动窗口是一种在 数组（或字符串）的连续部分 上进行处理，同时 复用之前计算结果 的技术。
与其为每个新子数组重新计算所有内容，你可以：

1. 计算第一个窗口的结果。
2. 通过 移除离开的元素 并 加入进入的元素 来向前滑动窗口。

就是这么简单。

何时使用滑动窗口

只要题目要求关于 子数组 / 子串 的某些信息，尤其是出现以下描述时，就可以使用：

• “大小为 K 的子数组”
• “任意 K 长度窗口的最大/最小和”

在这种情况下，朴素的做法是：

• 遍历所有可能的子数组。
• 每次都重新求和 → O(N·K) 时间。

使用滑动窗口，你只需增量更新结果，就能实现 O(N) 时间。

示例

考虑下面的数组：

[5, 2, 7, 1]
K = 3

第一个窗口 ([5, 2, 7]) → 和 = 14

滑动一步 →

• 离开的元素：5
• 新窗口：[2, 7, 1]
• 更新后的和：14 - 5 + 1 = 10

无需完整重新计算。

指针移动是如何工作的

固定大小的滑动窗口

设 k 为窗口大小。对每一步 i（从 i = k 开始）：

• 离开的元素 = arr[i - k]
• 进入的元素 = arr[i]

不需要显式的“左指针”；算术运算已经帮你处理了。

示例代码（C++）

double maxSumSubarray(vector nums, int k) {
    int windowSum = 0;

    // first window
    for (int i = 0; i (maxSum) / k;
}

只要你能把上面的步骤说清楚，就可以把它们翻译成任何语言的代码。

示例输入以检验你的理解

nums = [1, 12, -5, -6, 50, 3]
k = 4

窗口依次为：

1. [1, 12, -5, -6]
2. [12, -5, -6, 50]
3. [-5, -6, 50, 3]

每次滑动都移除一个元素并加入一个新元素，从而可以用简单的 减去 + 加上 操作来更新和（或其他聚合值），不需要额外的循环。

关键要点

滑动窗口技巧并非魔法，它其实就是：

“通过移除离开的元素并加入进入的元素来复用之前的结果。”

这样做可以避免冗余计算，为许多子数组/子序列问题实现线性时间解法。