前缀和不难，却很有⽤，主要⽤于处理数组区间的问题。
前缀和的思路是这样的，对于⼀个给定的数组 nums ，我们额外开辟⼀个前缀和数组进⾏预处理：
1
2
3
4
5
6
int n = nums.length;
// 前缀和数组
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++)
preSum[i + 1] = preSum[i] + nums[i];
这个前缀和数组 preSum 的含义也很好理解， preSum[i] 就是 nums[0..i-1] 的和。那么如果我们想求 nums[i..j] 的和，只需要⼀步操作preSum[j+1]-preSum[i] 即可，⽽不需要重新去遍历数组了。
回到这个⼦数组问题，我们想求有多少个⼦数组的和为 k，借助前缀和技巧很容易写出⼀个解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int subarraySum(int[] nums, int k) {
int n = nums.length;
// 构造前缀和
int[] sum = new int[n + 1];
sum[0] = 0;
for (int i = 0; i < n; i++)
sum[i + 1] = sum[i] + nums[i];
int ans = 0;
// 穷举所有⼦数组
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
// sum of nums[j..i-1]
if (sum[i] - sum[j] == k)
ans++;
return ans;
}
这个解法的时间复杂度 O(N^2) 空间复杂度 O(N)，并不是最优的解法。
优化的思路是：直接记录下有⼏个 sum[j] 和 sum[i] - k 相等，直接更新结果，就避免了内层的 for 循环。我们可以⽤哈希表，在记录前缀和的同时记录该前缀和出现的次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int subarraySum(int[] nums, int k) {
int n = nums.length;
// map：前缀和 -> 该前缀和出现的次数
HashMap<Integer, Integer>
preSum = new HashMap<>();
// base case
preSum.put(0, 1);
int ans = 0, sum0_i = 0;
for (int i = 0; i < n; i++) {
sum0_i += nums[i];
// 这是我们想找的前缀和 nums[0..j]
int sum0_j = sum0_i - k;
// 如果前⾯有这个前缀和，则直接更新答案
if (preSum.containsKey(sum0_j))
ans += preSum.get(sum0_j);
// 把前缀和 nums[0..i] 加⼊并记录出现次数
preSum.put(sum0_i,
preSum.getOrDefault(sum0_i, 0) + 1);
}
return ans;
}
这样，就把时间复杂度降到了 O(N)，是最优解法了。
