# 前缀和技巧
![](../pictures/souyisou.png) 相关推荐: * [如何去除有序数组的重复元素](https://labuladong.gitbook.io/algo) * [区间调度之区间合并问题](https://labuladong.gitbook.io/algo) 读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目: [560.和为K的子数组](https://leetcode-cn.com/problems/subarray-sum-equals-k) **-----------** 今天来聊一道简单却十分巧妙的算法问题:算出一共有几个和为 `k` 的子数组。 ![](../pictures/%E5%89%8D%E7%BC%80%E5%92%8C/title.png) 那我把所有子数组都穷举出来,算它们的和,看看谁的和等于 `k` 不就行了。 关键是,**如何快速得到某个子数组的和呢**,比如说给你一个数组 `nums`,让你实现一个接口 `sum(i, j)`,这个接口要返回 `nums[i..j]` 的和,而且会被多次调用,你怎么实现这个接口呢? 因为接口要被多次调用,显然不能每次都去遍历 `nums[i..j]`,有没有一种快速的方法在 O(1) 时间内算出 `nums[i..j]` 呢?这就需要**前缀和**技巧了。 ### 一、什么是前缀和 前缀和的思路是这样的,对于一个给定的数组 `nums`,我们额外开辟一个前缀和数组进行预处理: ```java 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]; ``` ![](../pictures/%E5%89%8D%E7%BC%80%E5%92%8C/1.jpg) 这个前缀和数组 `preSum` 的含义也很好理解,`preSum[i]` 就是 `nums[0..i-1]` 的和。那么如果我们想求 `nums[i..j]` 的和,只需要一步操作 `preSum[j+1]-preSum[i]` 即可,而不需要重新去遍历数组了。 回到这个子数组问题,我们想求有多少个子数组的和为 k,借助前缀和技巧很容易写出一个解法: ```java 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 循环: ```java 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 语句里的条件判断移项,这样写: ```java if (sum[j] == sum[i] - k) ans++; ``` 优化的思路是:**我直接记录下有几个 `sum[j]` 和 `sum[i] - k` 相等,直接更新结果,就避免了内层的 for 循环**。我们可以用哈希表,在记录前缀和的同时记录该前缀和出现的次数。 ```java int subarraySum(int[] nums, int k) { int n = nums.length; // map:前缀和 -> 该前缀和出现的次数 HashMap