1. 先把“连续一段”翻译成前缀和的差#

前缀和可以理解成从数组开头一路加到当前位置的账本。

假设当前走到位置 r，目前的前缀和用代码里的变量 pre 表示：

1
pre = nums[0] + nums[1] + ... + nums[r]

如果有一个更早的前缀和 oldSum，那么从它后面开始到 r 的这一段，和就是：

1
pre - oldSum

题目要这一段等于 k，所以就是：

1
pre - oldSum = k
2
oldSum = pre - k

这一步是这题最关键的翻译。

我现在会把它想成：当前前缀和 pre 已经站在这里了，我不需要猜子数组从哪里开始，只需要问一句——以前有没有出现过 pre - k 这一层？如果出现过，从那一层之后到当前位置，中间这一段就刚好是 k。

2. 哈希表里为什么存“次数”#

哈希表 mp 里存的不是某个前缀和有没有出现过，而是它出现过几次。

原因是同一个前缀和可能出现多次。尤其数组里允许负数和 0，前缀和完全可能加上去又降回来。每一次出现的位置都可以作为一个不同的子数组起点。

比如当前 pre = 1，k = 1，那我需要找的旧前缀和就是 0。如果 0 之前出现过两次，就说明有两个不同的起点，都能和当前位置组成一个和为 1 的子数组。

所以代码里不是：

1
如果 pre - k 出现过，答案 + 1

而是：

1
count += mp[pre - k]

出现过几次，就补几个答案。

3. 用示例跑一遍#

以 nums = [1, 1, 1]，k = 2 为例。

一开始先放一个 0 进去：

1
mp[0] = 1

这个 0 表示“数组还没开始之前的前缀和”。它听起来有点像凭空塞进去的，但非常有用：如果从数组开头加到当前位置刚好等于 k，那就需要这个 0 来配对。

过程如下：

最后答案是 2，对应 [1, 1] 的前两个和后两个。

这张表里最顺的一点是：每到一个位置，只关心当前 pre 和以前有没有 pre - k。不需要重新把所有子数组再加一遍。

4. C++ 写法#

1
class Solution {
2
public:
3
    int subarraySum(vector<int>& nums, int k) {
4
        unordered_map<int,int> mp;
5
        mp[0] = 1;
6
        int count = 0, pre = 0;
7
        for (auto& x:nums){
8
            pre += x;
9
            if (mp.find(pre - k) != mp.end()){
10
                count += mp[pre - k];
11
            }
12
            mp[pre]++;
13
        }
14
        return count;
15
    }
16
};

这份代码的顺序也要注意：先查 pre - k，再把当前 pre 存进去。

因为当前前缀和应该作为后面位置的“历史前缀和”，不能马上拿来和自己配对。特别是 k = 0 的时候，如果先存再查，很容易把空子数组也算进去，那就开始自我感动了。

5. 为什么不用滑动窗口#

这题看起来也像连续子数组，很容易想到滑动窗口。但这里 nums[i] 可以是负数，窗口变大时总和不一定变大，窗口缩小时总和也不一定变小。

滑动窗口好用的前提，通常是窗口变化和目标之间有某种单调关系。比如全是正数时，右边加一个数总和只会变大，左边去掉一个数总和只会变小。

这题没有这个保证，所以前缀和更稳：它不依赖数组的正负，只依赖一个事实——任意连续一段的和，都可以表示成两个前缀和的差。

6. 我这次记下的东西#

这题对我来说，重点不是背一句“前缀和 + 哈希表”，而是把问题翻译成：

1
当前前缀和 pre - 目标 k = 我需要找的旧前缀和

我脑子里可以把它想成当前这一层往回减，看看之前有没有哪一层能让中间这段刚好剩下 k。代码里则用哈希表把这个“一层层检查”的过程压成一次查表。

时间复杂度是 O(n)，每个数字只处理一次；额外空间是 O(n)，最坏情况下每个前缀和都不同，都要存在哈希表里。