和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

暴力破解法

老样子，先上代码

public static int subarraySum(int[] nums, int k) {
    int res = 0;
    for (int start = 0; start < nums.length; start++) {
        int sum = 0;
        for (int end = start; end >= 0; end--) {
            sum += nums[end];
            if (sum == k){
                res ++;
            }
        }
    }
    return res;
}

这里采用的是暴力破解法，先确定连续子数组的开头，接着结尾往数组后拉，和为k则返回结果加一。

前缀和+哈希表

public static int subarraySum(int[] nums, int k) 
    Map<Integer, Integer> preSumFreq = new HashMap<>();
    preSumFreq.put(0, 1);

    int preSum = 0;
    int count = 0;
    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;
}

牛逼的方法总是大佬想出来的，这里我重述一下力扣大佬的题解。

preSumFreq里面存放的key，value分别对应，“连续子数组的和”和“出现的次数”。

具体的做法是，preSum代表前缀和，接着获取前缀和为 preSum - k 的个数。

讲一下这里为什么要获取前缀和为preSum - k的个数：

首先，我们的目的是要求得和为 k 的子数组的个数，preSum从数组第一个数开始加之后，

preSum - (preSum - k) 的结果即为 k ，所以有多少个preSum - k，就有多少个和为k的子数组

对于一开始的情况，下标 0 之前没有元素，可以认为前缀和为 0，个数为 1 个，这样可以计算第一组preSum=k的情况，即preSum-k = 0，此时，因为前缀和中已经有存放了key为0，value为1的一组，这时候count加上这个value。