# 560. Subarray Sum Equals K (M) Given an array of integers `nums` and an integer `k`, return *the total number of continuous subarrays whose sum equals to `k`*. **Example 1:** ``` Input: nums = [1,1,1], k = 2 Output: 2 ``` **Example 2:** ``` Input: nums = [1,2,3], k = 3 Output: 2 ``` **Constraints:** * `1 <= nums.length <= 2 * 104` * `-1000 <= nums[i] <= 1000` * `-107 <= k <= 107` ### `Solution:` 那我把所有子数组都穷举出来，算它们的和，看看谁的和等于 `k` 不就行了，借助前缀和技巧很容易写出一个解法： ```java int subarraySum(int[] nums, int k) { 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]; int res = 0; // 穷举所有子数组 for (int i = 1; i <= n; i++) for (int j = 0; j < i; j++) // 子数组 nums[j..i-1] 的元素和 if (preSum[i] - preSum[j] == k) res++; return res; } ``` 这个解法的时间复杂度 `O(N^2)` 空间复杂度 `O(N)`，并不是最优的解法。不过通过这个解法理解了前缀和数组的工作原理之后，可以使用一些巧妙的办法把时间复杂度进一步降低。 注意前面的解法有嵌套的 for 循环： ```java for (int i = 1; i <= n; i++) for (int j = 0; j < i; j++) if (preSum[i] - preSum[j] == k) res++; ``` 第二层 for 循环在干嘛呢？翻译一下就是，**在计算，有几个 `j` 能够使得 `preSum[i]` 和 `preSum[j]` 的差为 `k`**。毎找到一个这样的 `j`，就把结果加一。 我们可以把 if 语句里的条件判断移项，这样写： ```java if (preSum[j] == preSum[i] - k) res++; ``` 优化的思路是：**我直接记录下有几个 `preSum[j]` 和 `preSum[i] - k` 相等，直接更新结果，就避免了内层的 for 循环**。我们可以用哈希表，在记录前缀和的同时记录该前缀和出现的次数。 ```java int subarraySum(int[] nums, int k) { int n = nums.length; // map：前缀和 -> 该前缀和出现的次数 HashMap preSum = new HashMap<>(); // base case preSum.put(0, 1); int res = 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)) res += preSum.get(sum0_j); // 把前缀和 nums[0..i] 加入并记录出现次数 preSum.put(sum0_i, preSum.getOrDefault(sum0_i, 0) + 1); } return res; } Amother Version: Prefix Sum + Hash Table - O(n) time, O(n) space class Solution { public int subarraySum(int[] nums, int k) { if (nums == null || nums.length == 0) return 0; int sum = 0; int count = 0; HashMap map = new HashMap<>(); map.put(0, 1); for (int i = 0; i < nums.length; i++) { sum += nums[i]; if (map.containsKey(sum - k)) { count += map.get(sum - k); } map.put(sum, map.getOrDefault(sum, 0) + 1); } return count; } Another Version: Prefix Sum + Hash Table - O(n) time, O(n) space class Solution { public int subarraySum(int[] nums, int k) { if (nums == null || nums.length == 0) return 0; int sum = 0; int count = 0; HashMap map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { sum += nums[i]; if (sum == k) { count++; } if (map.containsKey(sum - k)) { count += map.get(sum - k); } map.put(sum, map.getOrDefault(sum, 0) + 1); } return count; } ``` 比如说下面这个情况，需要前缀和 8 就能找到和为 `k` 的子数组了，之前的暴力解法需要遍历数组去数有几个 8，而优化解法借助哈希表可以直接得知有几个前缀和为 8。 [![](https://labuladong.github.io/algo/images/%E5%89%8D%E7%BC%80%E5%92%8C/2.jpg)](https://labuladong.github.io/algo/images/%E5%89%8D%E7%BC%80%E5%92%8C/2.jpg) 这样，就把时间复杂度降到了 `O(N)`，是最优解法了。 前缀和技巧就讲到这里，应该说这个算法技巧是会者不难难者不会，实际运用中还是要多培养自己的思维灵活性，做到一眼看出题目是一个前缀和问题。 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://junnie.gitbook.io/nine-chapter/6.array/560.-subarray-sum-equals-k-m.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.