题目：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 为出现的次数

---

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;
    }
}