力扣 500 和为 K 的子数组

Problem: 560.和为 K 的子数组

思路

前缀和 + 小技巧

解题过程

题目大意可以理解为，让找一个数组中的连续非空子数组的和为k的数量。

这里可以使用前缀和数组suf[]来快速找到符合条件的子数组头和尾。因为一个子数组(i,j)的大小为suf[j] - suf[i-1]，因此我们这里只需要找到suf[j] - suf[i-1] = k的两个数，那么题目就变成找到两个数的差为k。那么显而易见可以用哈希来找。

这里有个小技巧，我一开始存储的哈希是把suf[i]和i一起存了，于是变得判断当前的i是否大于哈希找出来的i（因为j>i-1)，就得多个查找过程，这样可能会超时，后面发现直接边查边存就不会有这种问题了，这个小技巧适用于查找过程中有下标大小影响的时候，因为ii比当前下班大的下标的数据还未存入，所以这个时候查询只会查找到比当前下标小的数据。

复杂度

• 时间复杂度: O(n)

• 空间复杂度:O(n)

Code

class Solution { public int subarraySum(int[] nums, int k) { int len = nums.length; int[] suf = new int[len + 1]; for(int i = 0; i < len; i++) { suf[i + 1] = nums[i] + suf[i]; } Map<Integer,Integer> map = new HashMap<>(); int ans = 0; for(int i = 0; i <= len; i++) { int dif = suf[i] - k; ans += map.getOrDefault(dif, 0); map.merge(suf[i], 1, Integer::sum); } return ans; } }