560.和为k的子数组

题目内容

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2

输出：2

示例 2：

输入：nums = [1,2,3], k = 3

输出：2

思路讲解

题目给我们一个数组和整数k，让我们找出和为k的子数组，即一个连续的序列。

一提到连续，我们容易想到滑动窗口，通过不断移动左右指针来求得序列和，但需要注意的一点是，题目中的数组值有可能是负数，使得我们没办法来把窗口和的变化来与k作比较来实现指针移动。

于是我们想到用前缀和来解决，遍历数组每个值并获取每个对应位置的前缀和。

什么是前缀和

这里用示例2来举例，nums = [1,2,3]，pre通常用来定义前缀和，得到这个数组pres=[1,3,6]，顾名思义就是遍历到当前数时包括前方所有数的总和。

问题的关键是k和前缀和有什么关系？

假设我们的数组长度是10，我们分别通过遍历记录了每个位置的前缀和（比如6索引代表的前缀和即0~6索引对应数组值的加和），聪明的你发现了，不同索引对应前缀和的差值，正好是两索引之间的数组和。

如果9索引的前缀和减去6索引的前缀和，不就是一个索引为7、8、9的连续子数组吗！

读到这里你可能茅塞顿开，但并不是恍然大悟，因为我得到了子数组的和，该如何记录呢？

每次对一个数操作时，需要判断的是它的前缀和减去它前面的某些数是否存在等于k的情况（公式：pre[i]-pre[x]=k，i是当前遍历到的值，x是0~i之间的某个数，并不确定），那么我们分析出了需要O(1)查找，想到了哈希表。

我们只要每次计算pre-k有没有在之前出现过。如果出现了，count就可以加上它出现的次数；如果没出现，就可以把它加入哈希表用于后面的查询。

这个表格可以帮你理解（nums = [1,2,3], k=3）

下面是代码实现

代码实现

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

如果对你有帮助记得点赞支持！