07 滑动窗口基础：定长窗口与可变窗口的统一框架

滑动窗口基础：定长窗口与可变窗口的统一框架

摘要

滑动窗口是双指针算法中覆盖最广、变体最多的子类型。本文从”为什么子数组问题能用滑动窗口”这一本质出发，推导定长和可变两类窗口的统一框架，通过 Maximum Average Subarray I、Minimum Size Subarray Sum 等题精确刻画”窗口扩张-收缩”的状态机模型，并重点分析”为什么 left 不需要回退”这一正确性基石。

---

第 1 章 为什么连续子数组问题需要滑动窗口

1.1 从枚举所有子数组谈起

连续子数组问题的暴力解法：枚举所有子数组的起点 left 和终点 right（$n^2$ 种组合），对每个子数组计算目标值。如果计算本身需要 $O(n)$，总时间是 $O(n^3)$；如果能 $O(1)$ 计算（如前缀和），总时间是 $O(n^2)$。

$O(n^2)$ 还能进一步优化吗？

关键问题：对于”找满足某条件的最短/最长子数组”，右端点 right 固定时，最优左端点 left* 是唯一确定的。当 right 增大时，left* 的变化方向是怎样的？

如果 left* 随 right 增大而单调不减（即 left* 只会原地不动或向右移动，不会向左回退），那么：

• 内层 left 不需要每次从 0 开始枚举
• 整个过程中 left 总共只向右移动了 $n$ 步
• 总操作次数 $O(n)$

这就是滑动窗口的本质：利用 left* 的单调性，使内层枚举从 $O(n)$ 降到 $O(1)$（摊销）。

1.2 什么条件下 left* 单调不减？

以”最短子数组使和 ≥ target”为例（所有元素为正整数）：

• 右端点固定为 r，最优左端点为 l*（满足 sum[l*, r] >= target 且 l* 尽量大）
• 当右端点增大为 r+1，nums[r+1] 加入，新的最优左端点 l** 是否 ≥ l*？

是的：sum[l*, r+1] = sum[l*, r] + nums[r+1] >= sum[l*, r] >= target。新的子数组 [l*, r+1] 已经满足条件，但它可能不是最短的——也许 [l*+1, r+1] 也满足，使得 l** 可以更大。因此 l** ≥ l*，单调性成立。

根本原因：所有元素为正整数，加入新元素后子数组和只增不减，满足条件的最短子数组的左端点只会右移。

生产避坑：滑动窗口需要元素非负

如果数组中有负数，加入新元素可能使和减小，满足条件的左端点可能需要回退，单调性不成立，滑动窗口失效。此类问题（如”和为 target 的连续子数组”，含负数）需要改用前缀和+哈希表。

---

第 2 章 定长滑动窗口

2.1 定长窗口的特征

定长窗口（Fixed-Size Sliding Window）：窗口大小始终固定为 $k$。每次移动时，窗口右端加入一个新元素，左端移除一个旧元素，整体向右滑动一步。

定长窗口通常解决的问题：

• “长度为 $k$ 的子数组中，最大/最小/平均值是多少？”
• “是否存在长度为 $k$ 的子数组满足某条件？“

2.2 LeetCode 643：子数组最大平均数 I

LeetCode 643 - Maximum Average Subarray I（简单）

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k。请你找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75000
解释：最佳连续子数组为 [12,-5,-6,50]，其平均值 (12-5-6+50)/4 = 51/4 = 12.75。

输入：nums = [5], k = 1
输出：5.00000

解法：

public double findMaxAverage(int[] nums, int k) {
    // 计算第一个窗口的和
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];
    }
 
    int maxSum = windowSum;
 
    // 滑动窗口：右端加入，左端移除
    for (int right = k; right < nums.length; right++) {
        windowSum += nums[right];         // 右端加入新元素
        windowSum -= nums[right - k];     // 左端移除旧元素（即 nums[left]，left = right - k + 1 - 1 = right - k）
        maxSum = Math.max(maxSum, windowSum);
    }
 
    return (double) maxSum / k;
}

时间复杂度：$O(n)$，每个元素加入窗口一次、移除窗口一次，共 $2n$ 次操作。 空间复杂度：$O(1)$，只维护当前窗口的和。

2.3 定长窗口的维护原则

定长窗口的”滑动”逻辑：

当 right 从 k 移动到 n-1：
    windowState += nums[right]       // 加入右端新元素
    windowState -= nums[right - k]   // 移除左端旧元素（即下标 right - k 的元素）
    更新答案

“左端旧元素”的下标是 right - k（不是 right - k + 1）：当 right = k 时，窗口是 [0, k]（长度 $k+1$），需要移除下标 0（即 nums[right - k] = nums[0]），窗口变为 [1, k]（长度 $k$）。

2.4 进阶：定长窗口中的最大/最小值——单调队列

前面的题只需维护窗口内的和，$O(1)$ 即可更新。但如果需要维护窗口内的最大值或最小值（如 LeetCode 239 Sliding Window Maximum），每次移动后暴力遍历窗口 $O(k)$，总时间 $O(nk)$，不够优。

这类题需要单调队列（Monotonic Deque）：维护一个从大到小的队列，队头始终是当前窗口的最大值。每次移动：

• 加入新元素时，弹出队列中所有小于新元素的元素（它们永远不会是后续窗口的最大值）
• 移除旧元素时，检查队头是否是过期元素（下标超出窗口范围），若是则弹出

这属于滑动窗口与单调队列的结合，超出本文范围，但概念上仍是”定长窗口”的延伸。

---

第 3 章 可变滑动窗口

3.1 可变窗口的特征

可变窗口（Variable-Size Sliding Window）：窗口大小动态变化，right 向右扩张，left 在满足/不满足某条件时向右收缩。

可变窗口通常解决的问题：

• “满足某条件的最短子数组（收缩找最小）”
• “满足某条件的最长子数组（扩张找最大，超出条件时收缩）“

3.2 LeetCode 209：长度最小的子数组

LeetCode 209 - Minimum Size Subarray Sum（中等）

给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [nums_l, nums_{l+1}, ..., nums_{r-1}, nums_r]，并返回其长度。如果不存在符合条件的子数组，返回 0。

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

输入：target = 4, nums = [1,4,4]
输出：1

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

3.3 从暴力到滑动窗口的演化

暴力解法（$O(n^2)$）：

int minLen = Integer.MAX_VALUE;
for (int left = 0; left < n; left++) {
    int sum = 0;
    for (int right = left; right < n; right++) {
        sum += nums[right];
        if (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            break;  // 找到满足条件的最短子数组，换下一个 left
        }
    }
}

观察暴力解法：对每个 left，右指针从 left 出发向右找第一个满足条件的 right*。当 left 增大为 left+1 时，新的 right* 会不会比原来小？

不会！ 因为 nums 全为正整数，移除 nums[left] 后子数组和减小，要重新满足条件，right 只需要原地或向右扩张，不会左移。

这就是 left* 的单调不减性。滑动窗口的代码直接体现这一点：

public int minSubArrayLen(int target, int[] nums) {
    int left = 0, windowSum = 0;
    int minLen = Integer.MAX_VALUE;
 
    for (int right = 0; right < nums.length; right++) {
        windowSum += nums[right];  // 右端扩张
 
        // 窗口满足条件时，收缩左端，找最短满足条件的子数组
        while (windowSum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
    }
 
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

时间复杂度：$O(n)$。right 从 0 到 $n-1$，共 $n$ 次外层循环。left 的总移动次数 $\le n$（单调右移，最多移动 $n$ 次）。总操作次数 $2n$，即 $O(n)$。

空间复杂度：$O(1)$。

3.4 状态机视角：理解代码逻辑

用状态机来理解可变滑动窗口：

状态：当前窗口 [left, right] 的和是否 >= target

初始状态：窗口为空，windowSum = 0

事件：right 右移（外层 for 循环）
    → 将 nums[right] 加入窗口，windowSum 增大
    → 检查条件：windowSum >= target？
        → 是：进入"收缩阶段"
        → 否：继续扩张

事件：left 右移（内层 while 循环）
    → 更新答案（当前窗口是满足条件的候选）
    → 将 nums[left] 移出窗口，windowSum 减小
    → 重新检查条件：直到 windowSum < target，退出收缩阶段

每次从”收缩阶段”退出后，窗口处于”刚刚不满足条件”的状态，等待 right 继续扩张。

3.5 “先扩张后收缩”还是”先收缩后扩张”？

上面的代码是”先扩张（right++），后收缩（left++）“。还有一种写法：

// 另一种写法：先检查再扩张
while (right < n) {
    // 收缩：当窗口满足条件时，尝试收小
    while (left <= right && windowSum >= target) {
        minLen = Math.min(minLen, right - left + 1);
        windowSum -= nums[left++];
    }
    // 扩张
    windowSum += nums[right++];
}

两种写法逻辑等价，但第一种（先扩张后收缩）更自然——right 的每次移动立即反映到窗口中，然后判断是否需要收缩。第二种容易因为边界处理失误出错。

推荐第一种写法：外层 for right，内层 while 收缩。

---

第 4 章 两类窗口的统一框架

4.1 通用模板

// 滑动窗口通用模板
int left = 0;
WindowState state = new WindowState();  // 窗口内的统计量（和、字符频次等）
int answer = /* 初始值 */;
 
for (int right = 0; right < n; right++) {
    // 1. 将 nums[right] 加入窗口，更新 state
    state.add(nums[right]);
 
    // 2. 判断是否需要收缩
    while (/* 窗口需要收缩的条件 */) {
        // 3. 更新答案（对于"最短满足窗口"类题，在此处更新）
        answer = updateAnswer(answer, right - left + 1);
 
        // 4. 将 nums[left] 移出窗口，更新 state
        state.remove(nums[left]);
        left++;
    }
 
    // 5. 对于"最长满足窗口"类题，在此处更新答案
    // answer = updateAnswer(answer, right - left + 1);
}

两类题的答案更新位置不同：

• “最短满足条件的子数组”（如 Minimum Size Subarray Sum）：在收缩时（内层 while 里）更新答案，因为收缩使窗口变短，此时窗口仍满足条件
• “最长满足条件的子数组”（如 Longest Substring Without Repeating Characters）：在外层 for 循环末尾更新答案，此时窗口是以 right 为右端的最长满足条件子数组

4.2 两类题的判断依据

问题类型	典型题目	收缩条件	答案更新位置
最短满足条件	Minimum Size Subarray Sum	窗口满足条件时收缩	内层 while 里（收缩前）
最长满足条件	Longest Substring Without Repeating Characters	窗口不满足条件时收缩（恢复满足）	外层 for 末尾

理解这个区别，是写对滑动窗口代码的关键。

---

第 5 章 LeetCode 1343：大小为 K 且平均值大于等于阈值的子数组数目

5.1 题目

LeetCode 1343 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold（中等）

给你一个整数数组 arr 和两个整数 k 和 threshold，请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3

输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出：6

5.2 解法：定长窗口

定长窗口 + 条件计数，直接套模板：

public int numOfSubarrays(int[] arr, int k, int threshold) {
    int windowSum = 0;
    int count = 0;
 
    // 初始化第一个窗口
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    if (windowSum >= (long) k * threshold) count++;
 
    // 滑动窗口
    for (int right = k; right < arr.length; right++) {
        windowSum += arr[right];
        windowSum -= arr[right - k];
        if (windowSum >= (long) k * threshold) count++;
    }
    return count;
}

注意：k * threshold 的比较用 long 防止溢出（k 和 threshold 最大可以是 $10^4$ 和 $10^4$，乘积达到 $10^8$，接近 int 上限，安全起见用 long）。

---

第 6 章 定长窗口 vs 可变窗口 vs 前缀和

6.1 三者的适用场景对比

方法	适用场景	时间	空间
定长滑动窗口	窗口大小固定为 $k$，维护窗口内统计量（和、最值等）	$O(n)$	$O(1)$
可变滑动窗口	找最短/最长满足条件的子数组，元素非负	$O(n)$	$O(1)$
前缀和 + 哈希表	找和等于/大于某值的子数组，可以有负数	$O(n)$	$O(n)$
前缀和 + 二分查找	找和大于等于某值的最短子数组，可以有负数	$O(n\log n)$	$O(n)$

遇到连续子数组问题，先判断元素是否有负数：

• 无负数：优先考虑滑动窗口（$O(n)$ 时间 $O(1)$ 空间）
• 有负数：考虑前缀和方案（空间换时间）

---

小结

本文建立了滑动窗口的统一框架：

• 定长窗口：外层 for right，每步加入 nums[right]、移除 nums[right-k]，维护窗口统计量
• 可变窗口：外层 for right（扩张），内层 while（收缩），利用左端点单调性实现 $O(n)$ 摊销
• 答案更新位置：最短满足子数组在收缩时更新，最长满足子数组在扩张后更新

下一篇进入滑动窗口的进阶场景：窗口内不仅有数值统计，还需要维护字符频次哈希表，处理”无重复字符”和”字符种类数量约束”等更复杂的窗口条件。