560 和为 K 的子数组

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

前缀和：nums 的第 0 项到 当前项 的和。
定义 prefixSum 数组，prefixSum[x]：第 0 项到 第 x 项 的和。

• prefixSum[x] = nums[0] + nums[1] +…+nums[x]
• prefixSum[x]=nums[0]+nums[1]+…+nums[x]

nums 的某项 = 两个相邻前缀和的差：

• nums[x] = prefixSum[x] - prefixSum[x - 1]
• nums[x]=prefixSum[x]−prefixSum[x−1]

nums 的 第 i 到 j 项 的和，有：

• nums[i] +…+nums[j]=prefixSum[j] - prefixSum[i - 1]
• nums[i]+…+nums[j]=prefixSum[j]−prefixSum[i−1]

当 i 为 0，此时 i-1 为 -1，我们故意让 prefixSum[-1] 为 0，使得通式在i=0时也成立：

• nums[0] +…+nums[j]=prefixSum[j]
• nums[0]+…+nums[j]=prefixSum[j]

题目的等价转化

不用求出 prefixSum 数组
其实我们不关心具体是哪两项的前缀和之差等于k，只关心等于 k 的前缀和之差出现的次数c，就知道了有c个子数组求和等于k。
遍历 nums 之前，我们让 -1 对应的前缀和为 0，这样通式在边界情况也成立。即在遍历之前，map 初始放入 0:1 键值对（前缀和为0出现1次了）。
遍历 nums 数组，求每一项的前缀和，统计对应的出现次数，以键值对存入 map。
边存边查看 map，如果 map 中存在 key 为「当前前缀和 - k」，说明这个之前出现的前缀和，满足「当前前缀和 - 该前缀和 == k」，它出现的次数，累加给 count。
代码
时间复杂度 O(n) 。空间复杂度 O(n)

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