High frequency interview questions -- subarray with sum K

The finger of the sword Offer II 010. And for k Subarray

Given an array of integers and an integer k , Please find the array with k The number of consecutive subarrays of .

Example 1：

Input :nums = [1,1,1], k = 2
Output : 2
explain : This question [1,1] And [1,1] For two different situations
Example 2：

Input :nums = [1,2,3], k = 3
Output : 2

Tips :

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

Ideas

Array ：0…i…j…end

When we want to judge j Whether there are conditions for the number , We just need to judge j The number minus 0 To i The number and （0<i<j） Is it equal to k You can judge whether there are conditions （ Section i+1 To j And ）.

So let's just go ahead i Record the sum of the numbers , As a prefix , Then use the one with relatively high efficiency hashmap Record prefix , You can quickly find the answer .

class Solution {
    
    public int subarraySum(int[] nums, int k) {
    
        HashMap<Integer,Integer> map = new HashMap<>(); 
        int pre = 0,count = 0;
        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);
            }
            // Judge whether it exists per key , If exist , Then take pre value +1, If it does not exist , Then create a , The value is 0
            map.put(pre,map.getOrDefault(pre,0)+1);   
        }
        return count;
    }
}

The code is the official answer , Record your understanding here