滑动窗口与前缀和

"连续子数组"是数组专题的高频题眼：求区间和、求和为 K 的子数组个数、求满足条件的最短子数组……暴力枚举都是 O(n²) 起。这篇文章讲两个能把复杂度压到 O(n) 的框架：前缀和管"快速算区间和"，滑动窗口管"快速找最优窗口"。

前缀和：O(1) 回答区间和

思想

先做一次 O(n) 预处理，把"从开头到 i 的累加和"存下来：

nums:   [ 1,  2,  3,  4,  5 ]
pre:  [0, 1,  3,  6, 10, 15 ]     pre[i] = nums[0] + ... + nums[i-1]

pre[0] = 0 是刻意留的哨兵位。有了它，任意区间 [i, j] 的和就是一次减法：

sum(i..j) = pre[j+1] - pre[i]
例：sum(1..3) = pre[4] - pre[1] = 10 - 1 = 9  →  2+3+4 = 9 ✓

实现：LeetCode 303 区域和检索

题目给出不可变数组，要求多次调用 sumRange(i, j)。如果不做预处理，每次调用 O(n)、m 次调用 O(n·m)；前缀和预处理一次 O(n)，之后每次 O(1)。

class NumArray {
    private final int[] pre;   // pre[i] = nums[0] + ... + nums[i-1]
 
    public NumArray(int[] nums) {
        pre = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            pre[i + 1] = pre[i] + nums[i];   // 递推构建
        }
    }
 
    public int sumRange(int left, int right) {
        return pre[right + 1] - pre[left];   // 一次减法拿到区间和
    }
}

时间 O(n) 预处理 + O(1) 单次查询；空间 O(n)。前缀和数组比原数组多一位，就是为了 left = 0 时减法不用特判——哨兵位是模板固定写法。

进阶：LeetCode 560 和为 K 的子数组

问"和恰好等于 k 的连续子数组有几个"，数组可能含负数（滑窗失效，后面解释为什么）。把前缀和反过来用：区间 (i, j] 的和等于 k 等价于 pre[j] - pre[i] == k，也就是在 j 之前找有多少个前缀和等于 pre[j] - k。用哈希表边扫边统计：

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    cnt.put(0, 1);                    // 空前缀：pre[0]=0 出现一次，覆盖"从头开始"的子数组
    int pre = 0, ans = 0;
    for (int x : nums) {
        pre += x;
        ans += cnt.getOrDefault(pre - k, 0);  // 之前出现过几次 pre-k，就有几个以当前位置结尾的解
        cnt.merge(pre, 1, Integer::sum);      // 必须先查询再插入，避免 k=0 时把自己算进去
    }
    return ans;
}

时间 O(n)，空间 O(n)。这是"前缀和 + 哈希表"组合的经典范式，后面哈希表专题还会遇到它的兄弟题（974）。

滑动窗口模板

为什么比暴力快

以 209 为例：找"元素和 ≥ target 的最短连续子数组"。暴力思路是枚举每个起点，向后累加到达标为止，O(n²)。但观察一个事实：当窗口从起点 i 向右扩张到达标后，起点换成 i+1 时，终点不必回头重新出发——窗口的右边界只进不退。于是左右指针各走 n 步，总操作 2n，整体 O(n)。

模板与逐行讲解（LeetCode 209）

public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    int ans = Integer.MAX_VALUE;
    int sum = 0;                  // 窗口 [left..right] 内元素之和
    int left = 0;
 
    for (int right = 0; right < n; right++) {   // 右指针每轮扩张一步，遍历整个数组
        sum += nums[right];                     // 1. 扩张：新元素进入窗口
 
        while (sum >= target) {                 // 2. 条件满足：尝试收缩
            ans = Math.min(ans, right - left + 1);  // 先记录当前窗口长度
            sum -= nums[left];                  // 3. 收缩：左端元素离开窗口
            left++;
        }
        // 循环到这里说明窗口已不满足条件，等下一轮右指针继续扩张
    }
    return ans == Integer.MAX_VALUE ? 0 : ans;  // 从未达标则返回 0
}

三个关键点：

外层 for 动右指针，内层 while 动左指针：右指针单调前进，左指针只在条件满足时前进且永不后退，两个指针各走 n 步，这是 O(n) 的根源。
先记录再收缩：进入 while 时窗口一定是满足条件的，必须先更新答案再缩。
while 不是 if：缩一次后可能仍满足条件（例如刚加进来的元素很大），要一路缩到不满足为止。

手动模拟一遍 nums = [2,3,1,2,4,3], target = 7：

right=0  窗口[2]      sum=2  不收缩
right=1  窗口[2,3]    sum=5  不收缩
right=2  窗口[2,3,1]  sum=6  不收缩
right=3  窗口[2,3,1,2] sum=8  达标 → ans=4，缩出 2 → sum=6 停
right=4  窗口[3,1,2,4] sum=10 达标 → ans=4，缩出 3 → sum=7 仍达标 → ans=3 [1,2,4]，缩出 1 → sum=6 停
right=5  窗口[2,4,3]  sum=9  达标 → ans=3，缩出 2 → sum=7 仍达标 → ans=2 [4,3]，缩出 4 → sum=3 停
最终答案 2

何时能用滑动窗口

滑动窗口不是万能的，它成立依赖两个条件：

求解对象是连续区间：子数组、子串。跳跃的子序列不适用。
窗口指标具备单调性：窗口扩大时指标单调变"好"或变"坏"，缩小时间反方向变化，这样收缩逻辑才确定。209 里"和随窗口扩大而增"就是单调性。

反例就是 560（数组含负数）：加入负数后窗口和不再随扩大单调增，"达标就收缩"的判定失效，所以只能退回前缀和 + 哈希。判断一道题"该滑窗还是该前缀和"，就问一句：窗口和（或窗口指标）是不是单调的？ 全正数单调 → 滑窗；含负数不单调 → 前缀和。

进阶提点：76 最小覆盖子串

76 是滑动窗口的字符串升级版：在 s 中找包含 t 全部字符（含重复次数）的最小子串。框架与 209 完全同构——右扩、达标、左缩——变化只在"达标"的判定上：需要维护窗口内各字符计数，并用一个变量记录"已满足的字符种类数"，种类数等于 t 的种类数即达标。

// 核心判定骨架（完整实现建议独立完成）
// need:  t 中每个字符需要的次数
// win:   当前窗口每个字符的数量
// valid: 窗口中"数量已达需求"的字符种类数
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    if (need.containsKey(c)) {
        win.merge(c, 1, Integer::sum);
        if (win.get(c).equals(need.get(c))) valid++;   // 该字符刚凑够
    }
    while (valid == need.size()) {                     // 全部凑够，尝试收缩
        if (right - left + 1 < minLen) { /* 更新答案窗口 */ }
        char d = s.charAt(left++);
        if (need.containsKey(d)) {
            if (win.get(d).equals(need.get(d))) valid--;  // 缩走后该字符不够了
            win.merge(d, -1, Integer::sum);
        }
    }
}

时间 O(|s| + |t|)（字符集有限，哈希操作近似 O(1)）。把 209 的"数值和"换成 76 的"字符计数"，你就掌握了滑动窗口一族的所有主干变体。

易错点清单

前缀和数组忘了多开一位哨兵，left=0 的区间减法越界。
560 中先插入当前前缀再查询，k=0 时会把空子数组错误计入（必须先查后插）。
209 的内层写成 if，只缩一次，漏掉更短窗口。
窗口长度算错：闭区间窗口 [left..right] 的长度是 right - left + 1。
含负数的数组硬套滑动窗口（单调性不成立）。

对应 LeetCode 题目

题号	题名	一句话考点
303	区域和检索 - 数组不可变	前缀和预处理 + O(1) 区间查询
560	和为 K 的子数组	前缀和 + 哈希计数，含负数不能滑窗
209	长度最小的子数组	滑动窗口正模板：右扩左缩
76	最小覆盖子串	字符计数版滑窗，valid 变量维护达标数
974	和可被 K 整除的子数组	560 的同族变体，前缀和对 K 取模

参考

代码随想录 · 数组专题