和为 K 的子数组为什么用前缀和加哈希表？

简化版

和为 K 的连续子数组可以用前缀和转化：若 prefix[j] - prefix[i] = k，则需要找之前出现过多少个 prefix[j] - k。用哈希表记录前缀和出现次数，一趟扫描即可统计答案，时间 O(n)。

详细版

遍历数组时维护当前前缀和 sum。以当前位置结尾、和为 k 的子数组数量，等于之前前缀和为 sum - k 的次数。哈希表 count 存 前缀和 -> 出现次数。

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);
    int sum = 0, ans = 0;
    for (int x : nums) {
        sum += x;
        ans += count.getOrDefault(sum - k, 0);
        count.put(sum, count.getOrDefault(sum, 0) + 1);
    }
    return ans;
}

初始化 count[0]=1 是为了统计从下标 0 开始的子数组。

完整版教学

一、为什么滑动窗口不适合所有情况

如果数组全是非负数，滑动窗口可以通过“和变大就缩小窗口”来找目标。但如果数组包含负数，窗口扩大可能让和变小，缩小可能让和变大，单调性失效。

例如 [1,-1,1]，窗口变化没有固定方向。此时要换思路，用前缀和表达任意连续子数组的和。

二、前缀和公式怎么来

定义 prefix[t] 为下标 0..t-1 的元素和。那么子数组 [i..j] 的和是：

sum(i..j) = prefix[j+1] - prefix[i]

要让它等于 k，就有 prefix[i] = prefix[j+1] - k。当我们扫描到当前位置的前缀和 sum 时，只需要知道之前有多少个前缀和等于 sum-k。

三、哈希表为什么存次数

同一个前缀和可能出现多次，每一次都对应一个不同的起点。例如 nums=[0,0], k=0，前缀和 0 会出现多次，答案是 3 个子数组：[0]、[0]、[0,0]。

扫描位置	需要 sum-k	已有次数	新增答案
初始	-	1	-
第 1 个 0	0	1	1
第 2 个 0	0	2	2

所以 Map 的 value 是次数，不是布尔值。

四、为什么先查再更新

扫描到当前位置时，要统计“以前的前缀和”作为起点。如果先把当前 sum 加进哈希表，就可能把空子数组也算进去，尤其当 k=0 时会多算。

正确顺序:
sum += nums[i]
ans += count[sum-k]
count[sum]++

这和两数之和的“先查再放”很像，都是为了避免当前状态匹配自己。

五、复杂度和溢出

每个元素只扫描一次，哈希查找和更新平均 O(1)，所以时间 O(n)，空间最坏 O(n)。如果数组元素和长度都很大，前缀和可能超过 int，工程代码可用 long 作为前缀和 key。

Map<Long, Integer> count = new HashMap<>();
long sum = 0L;

算法题若范围明确不会溢出，可以用 int；面试说出这个边界会更稳。

六、常见误区与追问

记忆钩子：当前前缀和是 sum，要凑出 k，就问过去有没有 sum-k。

误区：哈希表只存是否出现过。 题目统计个数，同一前缀和多次出现要累加次数。
误区：忘记初始化 count[0]=1。 会漏掉从数组开头开始、和正好为 k 的子数组。
误区：先更新当前前缀和再查。 k=0 时会把当前前缀和自己配自己，导致多算。
追问：为什么不用滑动窗口？ 有负数时窗口和不具备单调性，滑窗无法安全移动。
追问：如果只问是否存在怎么办？ 可以用 Set 存前缀和，查到 sum-k 即返回。
追问：空间能不能 O(1)？ 一般不能，因为需要记住历史前缀和分布；非负数组可改滑窗。

七、加强记忆

和为 K 的子数组要记住公式：当前前缀 sum - 历史前缀 old = k，所以 old = sum-k。哈希表存历史前缀和次数，先查再加，初始化 0 次数为 1。这个模板能迁移到“子数组和计数、同余计数、异或计数”等一大类题。

简化版

详细版