给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2
示例 2：
输入：nums = [1,2,3], k = 3 输出：2
解法一：暴力
public int subarraySum(int[] nums, int k) {
int count = 0;
//定义左指针
for (int left = 0; left < nums.length; left++) {
int sum = 0;
//右指针
for (int right = left; right < nums.length; right++) {
sum += nums[right];
if(sum > k){
break;
}
if(sum == k){
count++;
}
}
}
return count;
}解法二：前缀和
先计算出前缀和，再左右指针根据前缀和方便计算
public int subarraySum(int[] nums, int k) {
int count = 0;
//计算前缀和，构造数组
int[] preSum = new int[nums.length+1];
//起始元素设置为0，代表
preSum[0] = 0;
//初始化前缀和数组
for (int i = 0; i < nums.length; i++) {
preSum[i+1] = nums[i] + preSum[i];
}
//左指针
for (int left = 0; left < nums.length; left++) {
//右指针
for(int right = left; right < nums.length; right++){
//利用公式sum=preSum[right+1]−preSum[left]计算区间有无符合数据
if(preSum[right+1] - preSum[left] == k){
count++;
}
}
}
return count;
}解法三：前缀和+哈希
哈希是通过计算两个前缀和的差值是否为K，当为K的时候，count++
public int subarraySum(int[] nums, int k) {
int count = 0;
HashMap<Integer, Integer> preSumFreq = new HashMap<>();
//计算前缀和，构造数组，就是从
//为了防止开头第一个元素直接就是k，因为我们是先containKey，如果没有初始值，那就会漏一个结果
preSumFreq.put(0, 1);
int preSum = 0;
//初始化前缀和map，键是前缀和，值是该前缀和出现的频率。
for (int num : nums) {
preSum += num;
//判断有该元素是否是符合结果
if(preSumFreq.containsKey(preSum - k)){
count += preSumFreq.get(preSum - k);
}
preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
}
return count;
}