和为 K 的子数组有多少个？为什么用前缀和 + 哈希而不是滑动窗口？

简化版

统计数组里和恰好等于 K 的连续子数组个数(数组可能有负数)。用前缀和 + 哈希表:边遍历边算前缀和 sum,子数组 [l..r] 的和为 K ⟺ prefix[r+1] - prefix[l] = K ⟺ prefix[l] = sum - K。所以用哈希表记录每个前缀和出现的次数,遍历到当前 sum 时,查 sum - K 出现过几次,累加即可。O(n)。因为有负数,滑动窗口失效,必须用前缀和 + 哈希。

详细版

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);                     // 前缀和为 0 出现 1 次（空前缀）
    int sum = 0, res = 0;
    for (int x : nums) {
        sum += x;                        // 当前前缀和
        res += count.getOrDefault(sum - k, 0); // 有多少个前缀和 == sum-k
        count.merge(sum, 1, Integer::sum);     // 记录当前前缀和
    }
    return res;
}

sum - k:要找的「起点前缀和」——存在一个前缀和等于 sum-k,就有一个以当前位置结尾、和为 k 的子数组。
count.put(0, 1):初始化,处理「从头开始就和为 k」的子数组(sum - k == 0)。
先查后存:先累加答案,再把当前 sum 存入,避免把「自己」算进去。

完整版教学

一、把「区间和为 K」转成「两前缀和之差为 K」

这题的核心转化:子数组 [l..r] 的和 = prefix[r+1] - prefix[l]。要它等于 K:

prefix[r+1] - prefix[l] = K   ⟺   prefix[l] = prefix[r+1] - K

所以「找和为 K 的子数组」就变成「对每个右端点 r,找有多少个左端点 l 使 prefix[l] = prefix[r+1] - K」。也就是在已经出现过的前缀和里,找有多少个等于 当前前缀和 - K。用哈希表记录前缀和的出现次数,就能 O(1) 查询,总 O(n)。

二、哈希表记录「前缀和 → 出现次数」

遍历数组,维护当前前缀和 sum。用哈希表 count 记录每个前缀和值出现了多少次(注意是次数,不是是否出现——因为有负数,同一个前缀和可能出现多次,每次都对应一个合法起点)。对当前 sum:

查询:count[sum - k] 就是「以当前位置结尾、和为 k 的子数组个数」,累加进答案。
更新:把 sum 存入哈希表(次数 +1),供后面的位置查询。

三、为什么初始化 count[0] = 1(易错点)

count.put(0, 1) 是必须的,它处理「从数组开头到当前位置,整段和恰好为 K」的情况。这种子数组的左端点 l = 0,对应 prefix[0] = 0。如果不预置 count[0] = 1,当 sum == k(sum - k == 0)时就查不到这个起点,会漏算。可以理解为:空前缀(前 0 个元素)的和是 0,它出现了 1 次。这是本题最经典的坑。

四、为什么「先查后存」

顺序很重要:先累加答案 res += count[sum-k],再把当前 sum 存入。如果先存后查,当 k == 0 时会把「当前这个前缀和自己」算进去(sum - 0 == sum),导致一个长度为 0 的「子数组」被错误统计。先查后存保证查询时哈希表里只有「当前位置之前」的前缀和,对应真正的左端点。

五、为什么滑动窗口在这里失效(重点)

「和为 K 的子数组」很像滑动窗口题,但数组有负数时滑动窗口不能用。滑动窗口依赖单调性:「扩窗口和增大、缩窗口和减小」。有负数时,加入一个负数会让和变小、移出一个负数会让和变大,这个单调性被打破——无法根据「和太大/太小」决定扩还是缩。所以有负数求「和为定值的子数组」,只能用前缀和 + 哈希(它不依赖单调性,靠的是「两前缀差为 K」的等式)。

如果数组全为正数,求「和为 K 的子数组」或「和 ≥ K 的最短子数组」,滑动窗口也可以;但一旦可能有负数,认准前缀和 + 哈希。

六、复杂度与延伸

时间 O(n)、空间 O(n)(哈希表)。
延伸(同一套「前缀量 + 哈希」框架):
- 和能被 K 整除的子数组:记录前缀和的余数出现次数。
- 连续数组(0 和 1 数量相等):把 0 看成 -1,转成「和为 0 的最长子数组」,哈希记录前缀和首次出现的下标。
- 和为 K 的子数组异或版:前缀异或和 + 哈希。

七、从公式证明到手算闭环

这道题成立的核心是：扫描到右端 j 时，哈希保存此前所有前缀和频次；每个值为 sum-K 的旧前缀都对应一个以 j 结尾的合法子数组。先明确每个数组槽或哈希键的数学含义，代码中的下标偏移才不是死记硬背。

count[0] = 1
sum += a[j]
answer += count.get(sum - K, 0)
count[sum]++

带数字推演：[1,1,1]、K=2：前缀依次为 1、2、3，在 2 时找到旧前缀 0，在 3 时找到旧前缀 1，共 2 个。手算时同时列出原数组、辅助状态和本轮新增答案，能够直接发现端点偏一、初始化遗漏以及更新顺序错误。

核对维度	本题结论
正确性依据	扫描到右端 j 时，哈希保存此前所有前缀和频次；每个值为 sum-K 的旧前缀都对应一个以 j 结尾的合法子数组
复杂度	期望时间 O(n)，哈希空间 O(n)，可处理正数、零和负数
关键边界	必须先查询再写入当前前缀，避免 K=0 时把空区间算进去；包含负数时滑窗和不单调；总和与答案数都可能溢出

记忆钩子：不要先背代码，先说清辅助状态“代表哪一段”；公式只是把重叠部分消掉或把边界影响传播出去。

八、实现边界与测试策略

实现时最需要警惕的是：必须先查询再写入当前前缀，避免 K=0 时把空区间算进去；包含负数时滑窗和不单调；总和与答案数都可能溢出。这不是语法细节，而是决定算法是否仍满足题目语义的前提。

提交前应分别验证：

空数组或最小合法规模，确认哨兵位置和初始化。
查询或更新紧贴左、上边界，确认没有访问负下标。
查询或更新紧贴右、下边界，确认“终点后一位”不会越界。
包含 0、负数或重复前缀的样例，确认频次与取模语义。
大数输入，确认累计和、乘积或答案数量的整数类型足够。

如果需求从离线变成在线，或从单次恢复变成更新查询交错，原方法可能不再合适。此时应根据操作类型改用树状数组、线段树、二维结构或其他能维护动态状态的数据结构，而不是强行沿用静态前缀模型。

九、常见误区与追问

误区：哈希只存前缀和下标。 题目求数量，应存频次；求最长长度才常存最早下标。
误区：正数题和含负数题都能用同一滑窗。 负数让右扩和左缩不再单调。
误区：先存当前 sum 再查询更自然。 K=0 时会把当前前缀与自身组成空区间。
追问：count[0]=1 表示什么？ 表示选择“数组开始之前”的空前缀。
追问：为什么重复前缀都要计数？ 不同起点会形成不同子数组，不能去重。
追问：若只问是否存在怎么办？ 可用前缀集合，找到 sum-K 即返回。

十、加强记忆

和为 K 的子数组个数(可能有负数)用前缀和 + 哈希:子数组和为 K ⟺ prefix[l] = 当前sum - K,所以哈希记录前缀和出现次数,遍历时累加 count[sum-k]。两个坑:count[0]=1 初始化(处理从头和为 K)、先查后存(防 k=0 时算进自己)。O(n)。有负数滑窗失效(破坏单调性),必须用前缀和+哈希。延伸:能被 K 整除(记余数)、连续数组(0 当 -1)、异或版。

简化版

详细版