[question skimming diary] and a subarray of K

And for K Subarray

Given a Integers Array 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 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

【 Sliding window thinking 】

1. Determine the left and right boundaries
2. Find the conditions for sliding the window left and right

Suitable for solving related problems [ Continuous subarray ] subject

【 limitations 】 But in existence == negative == Cannot be used in an array of

Window sliding conditions ：

• while When the elements in the window exceed or do not meet the conditions The sliding window ;

• If there is a negative number , It is not certain that the left boundary is moved or Expand the right boundary

Ideas ： The prefix and + Hashtable

Applicable problem solving ： Subscript of circular array N when , Need to be used before N-1 The calculation result of the term （ and / product ）

How to save ？

1. The title clearly requires that no additional space is allowed , Directly modify the array in place
2. When space complexity is not limited , It is better to open up additional space for computing , avoid Data pollution
3. When calculating, you only need to obtain Last time Cumulative results of ===> Use Array Storage , Get the last element of the array every time
4. It is necessary to obtain each time during calculation A few or more times before The results are compared ===> Use Hashtable Storage , Reduce time complexity

Algorithm steps

Prefix and difference = The sum of successive subarrays

• Find the sum of successive subarrays as K <==> look for pre[j] - pre[i-1] == k Subscript pair of [i,j]
• pre[j] - pre[i - 1] == k Equivalent to pre[j] - k == pre[i - 1]
• At present The prefix and - k The income is front Of certain elements The prefix and

1. Hashtable hashmap ==> Save the existing prefix and The emergence of frequency , not only 1

   example ：[-1,1,0], k = 0

   • When traversing to the last element presum = 0

   • presum - k = 0 , Prefixes and are 0 Some of them are [-1,1] and [-1,1,0]

2. The current prefix and... Are incrementally calculated presum, And decide presum - k Whether in hashmap in , If exist , result + frequency hashmap[presum-k], And save the current prefix and presum To hashmap in

【 The border problem 】 if nums[0] = k , But now hashmap It's empty , No statistics ==> initialization hashmap by {0:1}

Code

class Solution {
    
public:
    int subarraySum(vector<int>& nums, int k) {
    
        map<int, int> hashmap;
        int presum = 0;
        int res = 0;
        hashmap[0] = 1;
        for(int i = 0;i < nums.size();i ++ ) {
    
            presum += nums[i];
            //  Judge presum-k Whether the resulting prefix and exist 
            if(hashmap.find(presum - k) != hashmap.end())
                res += hashmap[presum-k] ;
            
            //  Save the current prefix and 
            hashmap[presum] ++ ;
        }
        return res;
    }
};

Time complexity ：O(n)

Spatial complexity ：O(n)