读完本文，你能够去力扣拿下如下题目：
560.和为K的子数组
-----------
明天来聊一道简略却非常奇妙的算法问题：算出一共有几个和为 k 的子数组。
那我把所有子数组都穷举进去，算它们的和，看看谁的和等于 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)，并不是最优的解法。不过通过这个解法了解了前缀和数组的工作原理之后，能够应用一些奇妙的方法把工夫复杂度进一步升高。
二、优化解法
后面的解法有嵌套的 for 循环：
for (int i = 1; i <= n; i++) for (int j = 0; j < i; j++) if (sum[i] - sum[j] == k) ans++;第二层 for 循环在干嘛呢？翻译一下就是，在计算，有几个 j 可能使得 sum[i] 和 sum[j] 的差为 k。毎找到一个这样的 j，就把后果加一。
咱们能够把 if 语句里的条件判断移项，这样写：
if (sum[j] == sum[i] - k) ans++;优化的思路是：我间接记录下有几个 sum[j] 和 sum[i] - k 相等，间接更新后果，就防止了内层的 for 循环。咱们能够用哈希表，在记录前缀和的同时记录该前缀和呈现的次数。
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;}比如说上面这个状况，须要前缀和 8 就能找到和为 k 的子数组了，之前的暴力解法须要遍历数组去数有几个 8，而优化解法借助哈希表能够间接得悉有几个前缀和为 8。
这样，就把工夫复杂度降到了 O(N)，是最优解法了。
三、总结
前缀和不难，却很有用，次要用于解决数组区间的问题。
比如说，让你统计班上同学考试成绩在不同分数段的百分比，也能够利用前缀和技巧：
int[] scores; // 存储着所有同学的分数// 试卷满分 150 分int[] count = new int[150 + 1]// 记录每个分数有几个同学for (int score : scores) count[score]++// 结构前缀和for (int i = 1; i < count.length; i++) count[i] = count[i] + count[i-1];这样，给你任何一个分数段，你都能通过前缀和相减疾速计算出这个分数段的人数，百分比也就很容易计算了。
然而，略微简单一些的算法问题，不止考查简略的前缀和技巧。比方本文探讨的这道题目，就须要借助前缀和的思路做进一步的优化，借助哈希表去除不必要的嵌套循环。可见对题目的了解和细节的剖析能力对于算法的优化是至关重要的。
心愿本文对你有帮忙。