Leetcode-560: subarray with sum K

subject

Topic linking

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

 Input ：nums = [1,1,1], k = 2
 Output ：2

Example 2：

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

Problem solving

Method 1 ： The prefix and （ Overtime ）

class Solution {
    
public:
    int subarraySum(vector<int>& nums, int k) {
    
        int n=nums.size();
        vector<int> preSums(n+1);
        for(int i=0;i<nums.size();i++){
    
            preSums[i+1]=preSums[i]+nums[i];
        }
        int count=0;
        for(int i=1;i<=n;i++){
    
            for(int j=0;j<i;j++){
    
                if(preSums[i]-preSums[j]==k){
    
                    count++;
                }
            }
        }
        return count;
    }
};

Method 2 ： The prefix and + Hashtable

The red part is the sum we require k Subarray

If the prefix sum currently traversed is presum, So just know presum-k That's enough , Add presum-k The number of
adopt map To maintain a prefix and The number of

class Solution {
    
public:
    int subarraySum(vector<int>& nums, int k) {
    
        unordered_map<int,int> map;
        map[0]=1;// Prefixes and are 0 The number of 1
        int preSum=0;
        int count=0;
        for(int num:nums){
    
            preSum+=num;
            if(map.count(preSum-k)){
    // Add prefix and as preSum-k The number of 
                count+=map[preSum-k];
            }
            map[preSum]++;
        }
        return count;
    }
};