帖子会长期保持更新，只要是带娃的间隙就会偷偷上来更一下，尽量保持每周两更。
本期我们分享 面试经典题目–前缀和数组
由于太多人加我 VX，我也创建了一个算法工作交流群，大家感兴趣可以加我拉你进群
我的 VX：sxxzs3998 不管是具体的题目讨论还是给帖子的建议和拍砖，或者想进群都欢迎添加（记得加我要备注 v2 ）
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
那我把所有子数组都穷举出来，算它们的和，看看谁的和等于 k 不就行了。
关键是，如何快速得到某个子数组的和呢，比如说给你一个数组 nums，让你实现一个接口 sum(i, j)，这个接口要返回 nums[i..j] 的和，而且会被多次调用，你怎么实现这个接口呢？
因为接口要被多次调用，显然不能每次都去遍历 nums[i..j]，有没有一种快速的方法在 O(1) 时间内算出 nums[i..j] 呢？这就需要前缀和技巧了。
前缀和的思路是这样的，对于一个给定的数组 `nums`，我们额外开辟一个前缀和数组进行预处理：
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，借助前缀和技巧很容易写出一个解法：
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)`，并不是最优的解法。不过通过这个解法理解了前缀和数组的工作原理之后，可以使用一些巧妙的办法把时间复杂度进一步降低。