题目：subarray-sum-equals-k

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

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

示例 1：

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

示例 2：

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

解题思路

前缀和 + 哈希表

1. 遍历数组，依次计算从开始到下标 i 的前缀和
2. 如果中间某段和为 k ，那必然有 sum(nums[0]...nums[i]) - k = 前面的某（几）个前缀和
3. 把前缀和存 hashMap ， key 为 前缀和， value 为出现的次数

例如，对于：nums = [1,2,0,3,-1,-2,3], k = 5

数组：  1  2  0  3 -1 -2  3 
前缀和：1  3  3  6  5  3  6 
target：
当 i=0， preSum = 1， target = 1 - 5 = -4， map 中没有 -4，不加 count， map 中加入 1
当 i=1， preSum = 3， target = 3 - 5 = -2， map 中没有 -2，不加 count， map 中加入 3
当 i=2， preSum = 3， target = 3 - 5 = -2， map 中没有 -2，不加 count， map 中加入 3【第二次出现】
当 i=3， preSum = 6， target = 6 - 5 = 1， map 中有 1， count += 1， map 中加入 6
当 i=4， preSum = 5， target = 5 - 5 = 0， map 中有 0， count += 1， map 中加入 5
当 i=5， preSum = 3， target = 3 - 5 = -2， map 中没有 -2，不加 count， map 中加入 3【第三次出现】
当 i=6,  preSum = 6， target = 6 - 5 = 1， map 中有 1， count += 1， map 中加入 6

可以发现，当数组存在负数时，同一个前缀和是可以多次出现的，所以需要用 map 来存储前缀和出现的次数。当找到一个 target 时，要加上该前缀出现的次数，而不是加 1。

如果只写 count++，意味着只要在哈希表中找到了目标前缀和，就认为只找到了一个满足条件的子数组。但实际上，如果这个目标前缀和在前面已经出现过 3 次，说明以当前元素为结尾的有效子数组有3个不同的起点。

Java 实现

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int preSum = 0;
        
        // key: 某个前缀和   value: 该前缀和出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        
        // 【核心初始化】
        // 表示前缀和为 0 的情况出现过 1 次。
        // 这对应了子数组直接从索引 0 开始，且和刚好等于 k 的合法情况。
        map.put(0, 1);
        
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            int target = preSum - k;
            if (map.containsKey(target)) {
                count += map.get(target);
            }
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        
        return count;
    }
}