leetcode：560. Subarray with and K

Title source

• leetcode：560. And for K Subarray

Title Description

class Solution {
    

public:
    int subarraySum(vector<int>& nums, int k) {
    
        return process(nums, 0, k);
    }
};

title

A necessary condition for the use of double pointers and sliding windows is the ability to iterate step by step , Determines the direction in which the window shrinks , There are negative numbers , I didn't know it was the left side , Or the right side shrinks

enumeration

Ideas ： Enumerate all the subarrays , Calculate the sum of them , Look whose sum is equal to k

Enumerate the left and right boundaries

class Solution {
    
public:
    int subarraySum(vector<int>& nums, int k) {
    
        int len = nums.size();
        int cnt = 0;
        for (int left = 0; left < len; ++left) {
    
            for (int right = left; right < len; ++right) {
    
                
                int sum = 0;
                for (int i = left; i <= right; ++i) {
    
                    sum += nums[i];
                }
                
                if(sum == k){
    
                    cnt++;
                }
            }
        }
        return cnt;
    }
};

Counting while enumerating （ Also timeout ）

Fix the starting point first , Then enumerate the right boundary , The time complexity is reduced by one dimension

class Solution {
    
public:
    int subarraySum(vector<int>& nums, int k) {
    
        int len = nums.size();
        int cnt = 0;
        for (int left = 0; left < len; ++left) {
    
            int sum = 0;
            for (int right = left; right < len; ++right) {
    
                sum += nums[right];
                if(sum == k){
    
                    ++cnt;
                }
            }
        }
        return cnt;
    }
};

How to optimize ？ The key is how to quickly get the sum of a certain subarray , We can also use the prefix and to solve

The prefix and

What are prefixes and

For a given array num, We add a prefix and array to preprocess

int n = nums.length;
//  Prefixes and arrays 
std::vector<int> preSum(n + 1, 0);
preSum[0] = 0;
for (int i = 0; i < n; i++)
    preSum[i + 1] = preSum[i] + nums[i];

preSum[i] Namely nums[0..... i-1] And . If we want to ask for nums[i...j] And , Just ask for preSum[j+1] - preSum[i] that will do , Instead of traversing the array again

class Solution {
    
public:
    int subarraySum(vector<int>& nums, int k) {
    
        int len = nums.size();
        //  Construct prefixes and 
        std::vector<int> preSum(len + 1);
        preSum[0] = 0;
        for (int i = 0; i < len; ++i) {
    
            preSum[i + 1] = preSum[i] + nums[i];
        }
        
        int cnt = 0;
        //  Enumerate all subarrays 
        for (int left = 0; left < len; ++left) {
    
            for (int right = left; right < len; ++right) {
    
                if(preSum[right + 1] - preSum[left] == k){
    
                    ++cnt;
                }
            }
        }
        return cnt;
    }
};

class Solution {
    
public:
    int subarraySum(vector<int>& nums, int k) {
    
        int len = nums.size();
        //  Construct prefixes and 
        std::vector<int> preSum(len + 1);
        preSum[0] = 0;
        for (int i = 0; i < len; ++i) {
    
            preSum[i + 1] = preSum[i] + nums[i];
        }
        
        int cnt = 0;
        //  Enumerate all subarrays 
        for (int end = 1; end <= len; ++end) {
    
            for (int start = 0; start < end; ++start) {
    
                if(preSum[end] - preSum[start] == k){
    
                    ++cnt;
                }
            }
        }
        return cnt;
    }
};

It's over time

The prefix and + Hash

Because we only care about times , Don't care about the specific solution , So we can use the hash table to speed up the operation .

Main idea ： The calculation includes the prefix of the current tree and the following , Let's check before the current tree , How many prefixes are there and equal to preSum - k Well ？

class Solution {
    
public:
    int subarraySum(vector<int>& nums, int k) {
    
        std::vector<int> preSum(nums.size() + 1);
        preSum[0] = 0;
        for (int i = 0; i < nums.size(); ++i) {
    
            preSum[i + 1] = preSum[i] + nums[i];
        }
        
        std::unordered_map<int, int> map; // key  Prefix and ,value Is prefix and is key The number of , The problem turns into and k The problem of 
        map[0] = 1;
        int cnt = 0;
        for (int i = 1; i < preSum.size(); ++i) {
    
            if(map.count(preSum[i] - k)){
    
                cnt = cnt + map[preSum[i] - k]; //  If there is a connection with the current prefixSum[i] The difference is k Of , Then add its number 
            }
            ++map[preSum[i]];
        }
        return cnt;
    }
};

Implement with recursion ：

class Solution {
    
    int process(vector<int>& nums, int target, int currSum, int idx, std::unordered_map<int, int> &map){
    
        if(idx == nums.size()){
    
            return 0;
        }

        // Current prefix and 
        currSum += nums[idx];

        int res = 0;
        res += map[currSum - target];
        ++map[currSum];
        res += process(nums, target, currSum, idx + 1, map);
        return res;
    }
public:
    int subarraySum(vector<int>& nums, int k) {
    
        std::unordered_map<int, int> map; // key  Prefix and ,value Is prefix and is key The number of , The problem turns into and k The problem of 
        map[0] = 1;
        return process(nums, k, 0, 0, map);
    }
};