和为 K 的子数组
什么是前缀和
对于一个给定的数组 nums，如何快速得到某个子数组 nums[i..j] 的和呢? 这就需要前缀和技巧了。
额外开辟一个前缀和数组进行预处理：
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] 即可，而不需要重新去遍历数组了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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
|
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, pre = 0;
// 前缀和 -> 该前缀和出现的次数
Map < Integer, Integer > mp = new HashMap < > ();
mp.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
// 这是我们想找的前缀和 nums[0..j]
if (mp.containsKey(pre - k)) {
count += mp.get(pre - k);
}
// 把前缀和 nums[0..i] 加入并记录出现次数
mp.put(pre, mp.getOrDefault(pre, 0) + 1);
}
return count;
}
}
|
差分
如果需要快速让数组中某个区间加上一个数，就需要用到差分。
一维差分
首先我们需要一个差分数组，这个差分数组的前缀和数组刚好就是原数组，有点类似前缀和的逆操作？
1
2
|
for (int i = 1; i <= n; i++)
B[i] = A[i] - A[i - 1];
|
https://leetcode.cn/tag/prefix-sum/problemset/