560. 和为K的子数组

暴力法（连暴力法都没想出来……）

class Solution {public int subarraySum(int[] nums, int k) {int count=0;int len = nums.length;for(int i=0; i<len; i++) {int sum=0;for(int j=i; j<len; j++) {sum+=nums[j];if(sum == k) {count++;}}}return count;}
}

• 力扣官方
  

前缀和 + 哈希表优化

• 前缀和 基础知识

前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和
首先做一个预处理，定义一个sum[]数组，sum[i]代表a数组中前i个数的和。 sum[r+1]-sum[l]就是【L，R】的区间和

sum[r] = a[1] + a[2] + a[3] + a[l-1] + a[l] + a[l + 1] ...... a[r];
sum[l - 1] = a[1] + a[2] + a[3] + a[l - 1];
sum[r] - sum[l - 1] = a[l] + a[l + 1] + ......+ a[r];

• 本题前缀和的使用

通过计算前缀和，我们可以将问题转化为求解两个前缀和之差等于k的情况。

通过遍历数组，计算每个位置的前缀和，并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中，我们检查是否存在prefixSum[j] - k的前缀和，如果存在，说明从某个位置到当前位置的连续子数组的和为k， 我们将对应的次数累加到结果中。

这样，通过遍历一次数组，我们可以统计出和为k的连续子数组的个数，并且时间复杂度为O(n)，其中n为数组的长度。

实际做题的时候prefixSum[i]不一定只能表示下标为 0 - i-1 的数组元素和，也可以表示 0-i 。本题就是表示 0-i。

• preSum[]数组

class Solution {public int subarraySum(int[] nums, int k) {int[]preSum = new int[nums.length]; preSum[0] = nums[0];int count=0;HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();map.put(0,1);for(int i=0; i<nums.length; i++) {if(i!=0) preSum[i] = preSum[i-1]+nums[i];int pre = preSum[i];if(map.containsKey(pre-k)) {count += map.get(pre-k);}map.put(pre, map.getOrDefault(pre,0)+1);}return count;}
}

【重要】if(map.containsKey(pre-k)) ：是否存在prefixSum[j] - k的前缀和，如果存在，说明从某个位置到当前位置的连续子数组的和为k

map: <前缀和，数量> // 初始化前缀和为0的次数为1

• 本题也可以不使用数组

public class Solution {public int subarraySum(int[] nums, int k) {int count = 0, pre = 0;HashMap < Integer, Integer > mp = new HashMap < > ();mp.put(0, 1);for (int i = 0; i < nums.length; i++) {pre += nums[i];if (mp.containsKey(pre - k)) {count += mp.get(pre - k);}mp.put(pre, mp.getOrDefault(pre, 0) + 1);}return count;}
}作者：力扣官方题解