前缀和 + 哈希：子数组问题的终极模板

一句话结论（30s）

子数组和问题的万能模板是”前缀和 + 哈希表”，因为任意子数组和等于两个前缀和之差，用哈希表存已见前缀和，就能把 O(n²) 的暴力搜索降到 O(n)。

核心原理（2min）

sum[i, j] = prefix[j+1] - prefix[i]。遍历时对当前 prefix，查哈希表里有多少个 prefix - k，命中即说明存在和为 k 的子数组。模板只需改两处：①哈希表存什么 key（前缀和值 / 前缀和模值 / …）；②找哪个目标值（prefix - k）。

💭 思考：看到什么信号该想到「前缀和 + 哈希表」？—— 只要题目在问「连续子数组 / 子区间」的和满足某个条件（等于 k、被 k 整除、和为 T），暴力都得 O(n²) 枚举所有起点终点。这时候反问一句：能不能不枚举「起点 + 终点」，只枚举「终点」？子数组和 = 两个前缀和之差，说明枚举所有前缀和（O(n) 个）就能覆盖所有子数组和，剩下的「找差」交给哈希表 O(1) 查。所以信号是「区间 + 求和 + 连续」，套路是「前缀和 + 哈希查差」。

底层深入（5-10min）

前缀和的本质

前缀和 prefix[i] = nums[0] + nums[1] + ... + nums[i-1]。任意子数组 [i, j] 的和：

sum[i, j] = prefix[j+1] - prefix[i]

任意子数组和 → 两个前缀和的差。 这就是前缀和的核心洞察。为什么这个转化这么值钱？ 因为”枚举所有子数组”是 O(n²)，而”枚举所有前缀和”只有 O(n)——把求和问题降维成”两数之差”，就为后面用哈希表 O(1) 查差打好了地基。

和为 K 的子数组

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);             // prefix=0 出现一次（处理从头开始的子数组）
    int prefix = 0, count = 0;
    for (int num : nums) {
        prefix += num;
        count += map.getOrDefault(prefix - k, 0);
        map.put(prefix, map.getOrDefault(prefix, 0) + 1);
    }
    return count;
}

逻辑：遍历到位置 j 时，当前前缀和是 prefix。之前有多少个位置 i 的前缀和等于 prefix - k？如果等于，那 [i+1, j] 的和就是 prefix - (prefix-k) = k。一次遍历，O(n)，用哈希表替代了 O(n²) 的暴力搜索。为什么 map.put(0, 1) 这句不能省？ 因为”从头开始的子数组”对应的前缀和差是 prefix - 0，不预置 0 就会漏掉所有以第一个元素开头的合法子数组。

图景

输入: [1, 2, 3, -2, 5], k = 5

位置 0: prefix=1, 找 1-5=-4 → 0 个
位置 1: prefix=3, 找 3-5=-2 → 0 个
位置 2: prefix=6, 找 6-5=1  → 有! prefix[0]=1 → [2,3]子数组=5 (索引1到2)
位置 3: prefix=4, 找 4-5=-1 → 0 个
位置 4: prefix=9, 找 9-5=4  → 有! prefix[3]=4 → [2,3,-2,5]子数组? 等等...
                               也有 prefix=9? 不对，9-5=4, prefix[3]=4 → [4,4] 即 [5]=5
结果: 2 (子数组 [2,3] 和 [5])

💭 思考：为什么这题能把「枚举所有子数组」一步到位换成「枚举前缀和」？—— 先想清楚定义：sum[i,j] = prefix[j+1] - prefix[i]。那么「存在和为 k 的子数组」就等价于「存在两个前缀和，它们的差是 k」。遍历到位置 j 时，prefix 已知，差的另一头必须是 prefix - k，于是只要问：之前出现过的前缀和里有没有 prefix - k？有几个，就有几个以 j 结尾的和为 k 的子数组。这一层「把区间和翻译成两数之差」的转化，是后面所有变体（模 k、和 T）共用的那一步。

可被 K 整除的子数组

模运算的等价条件：(prefix[j] - prefix[i]) % K == 0 ↔ prefix[j] % K == prefix[i] % K。

直接存前缀和的模值。只需把 HashMap 的 key 从”前缀和值”变成”前缀和模 K 的值”。

💭 思考：为什么「能被 K 整除」要换成「模值相同」来判？—— 直接按定义要判 (prefix[j]-prefix[i]) % K == 0，但「差」是浮动的，没法用一个 key 存下来。于是把「差能被 K 整除」翻译成「两个数同余」：(a-b) % K == 0 当且仅当 a % K == b % K。一旦转成同余，key 就固定成 prefix % K，又回到了「查相等」的老套路——这正是模板里说的「只改 key」：value 不变，把「查差」换成「查同余」。

连续子数组和为 T

一般化为：找 prefix[j] - prefix[i] == T → 找 prefix[i] == prefix[j] - T。模板不变。

总结

前缀和 + 哈希表组合把”子数组和条件判断”从 O(n²) 降到 O(n)。模板只改两处：①哈希表存什么 key（前缀和值 / 前缀和模值 / …）；②找 key = 当前前缀和 - 目标值。

章末提问

1. 为什么子数组和问题一用前缀和就能从 O(n²) 变 O(n)？ 结论：因为”枚举子数组”需要两层循环，而”子数组和 = 两个前缀和之差”后只需一层循环枚举前缀和，再用哈希表 O(1) 查差。

2. 为什么初始化要 map.put(0, 1)？ 结论：因为前缀和 0 出现一次，代表”从数组头开始的子数组”这个合法情况；不预置会漏掉所有起点为下标 0 的子数组。

3. 可被 K 整除的子数组，为什么可以只存”前缀和模 K”？ 结论：因为 (prefix[j] - prefix[i]) % K == 0 等价于 prefix[j] % K == prefix[i] % K；所以只要两个前缀和同余，它们之间的子数组和就能被 K 整除，key 换成模值即可。