剑指 Offer II 010. 和为 k 的子数组

剑指 Offer II 010. 和为 k 的子数组

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

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
示例 2 :

输入:nums = [1,2,3], k = 3
输出: 2

提示:

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

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

有点像动态规划的思想，将已经有的结果存放在 map 中，当有存在 pre - k 的数 在 map 中存在时，说明存在连续的数组，让 count 加上 pre - k 出现的次数。

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map map = new HashMap<>();
        map.put(0, 1);
        int count = 0, pre = 0;
        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;
    }
}