560 and K

Give you an array of integers nums And an integer k , Please count and return The array is k The number of consecutive subarrays of .

The prefix and ：nums Of the 0 Item to Current item And .
Definition prefixSum Array ,prefixSum[x]： The first 0 Item to The first x term And .

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

nums An item of = The difference between the sum of two adjacent prefixes ：

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

nums Of The first i To j term And , Yes ：

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

When i by 0, here i-1 by -1, We deliberately let prefixSum[-1] by 0, Make the general formula in i=0 The time is also established ：

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

Equivalent transformation of the topic

There is no need to find prefixSum Array
In fact, we don't care which two prefixes have a difference equal to k, Only care is equal to k The number of occurrences of the difference between the prefix and c, I know there is c The sum of subarrays is equal to k.
Traverse nums Before , We let -1 The corresponding prefix and are 0, This general formula also holds in the boundary case . That is, before traversal ,map Initial placement 0:1 Key value pair （ Prefixes and are 0 appear 1 Time ）.
Traverse nums Array , Find the prefix sum of each term , Count the corresponding occurrence times , Store in key value pairs map.
View while saving map, If map in key by 「 The current prefix and - k」, Explain the prefix and , Satisfy 「 The current prefix and - The prefix and == k」, The number of times it appears , Add up count.
Code
Time complexity O(n) . Spatial complexity 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;
    }
    
}