560. 和为 K 的子数组

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

不能用二分，因为前缀和未必递增。

**不能用滑动窗口，因为窗口缩小的条件按理是和大于k，结束条件是小于等于k。假设此时窗口是[-2, 1, 3]， k=4，此时窗口和为2，小于4，所以停止收缩，这样就错过了[1,3]这个答案。**本质是因为有负数。

前缀和+哈希表

前缀和之差即连续子数组的和。count存储该前缀和出现的次数，map存储前缀和及其次数的映射。 对于当前元素，计算当前元素的前缀和，并检查是否存在值为pre - k（pre是当前的前缀和）的前缀和， 如果存在，说明找到了一个和为k的连续子数组，count+1。每次都要更新当前前缀和的出现次数。

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0; // 初始化计数器和前缀和
        Map<Integer, Integer> mp = new HashMap<>(); // 用于存储前缀和及其出现次数的哈希表
        // 初始化前缀和为0时的出现次数为1。重点。
        mp.put(0, 1); 

        for (int i = 0; i < nums.length; i++) {
            pre += nums[i]; // 计算当前元素的前缀和

            // 如果存在前缀和为 pre - k，则说明从该前缀和到当前前缀和的子数组和为 k。
            // 注意数组中可能有负数，所以前缀和未必是递增的，所以可能会有多个前缀和pre-k
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k); // 增加计数器
            }

            // 更新当前前缀和的出现次数
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }

        return count; // 返回满足条件的子数组个数
    }
}

• 时间复杂度：O(n)，其中 n 为数组的长度。我们遍历数组的时间复杂度为 O(n)，中间利用哈希表查询删除的复杂度均为 O(1)，因此总时间复杂度为 O(n)。
• 空间复杂度：O(n)，其中 n 为数组的长度。哈希表在最坏情况下可能有 n 个不同的键值，因此需要 O(n) 的空间复杂度。