LeetCode题解——和为 k 的子数组

更新一篇发布在力扣上的题解，900+的watch记录一波，题目链接：

https://leetcode-cn.com/problems/QTMn0o/

解题思路

1、 本题需要求出子数组之和为k的数组个数，如果限定了只有正数那么可以直接使用滑动窗口来解决，但这里可能存在负数，因此每次加入值不一定会增大和值，减去值不一定会减小和值；

2、 先看一个例子，对于数组【1，2，3，4，5】，按照题目要求求解。我们可以先统计一下前n项的和值出现的次数，也就是所谓的前缀和，这里将前缀和为0也统计进来：

1） 此时假设k=6，我们肉眼可见的数组和值为6的是【1，2，3】，那么对应到前缀和里面就是 3 这个位置，它其实可以看成 3 - 0 得到的区间和值；

2） 再假设k=7，那么我们可以发现数组和值为7的是【3，4】，此时我们可以发现在前缀和中没有找到和值为7的，那么说明该子数组的起始位置并非0；此时按照滑动窗口的思路就应该移动左指针，当左指针移动到索引2时就可以发现，索引2、3构成的子数组是满足条件的，借助上一个假设我们可以发现这里的和值7其实可以通过 4 － 2 来得到，因此我们实际上可以通过前缀和的差值来得出各个区间的和值，也就可以轻易得到和值为k的子数组了。

3、 具体解题上我们还应该考虑前n项和重复出现的情况，因此这里需要使用hash表来进行前缀和的统计，并且在初始化时应该写入(0，1)，否则当子数组起始位置为0时将无法被匹配到；接着我们可以确定下来每次寻找子数组时应该在hash表中寻找的键值是sum-k，因为直接寻找k只可以找到那些起始位置为0的子数组，而寻找sum-k因为我们事先插入了一个0的键值，因此这里也不会忽略掉这种情况。

参考代码：

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