Subarray Sum Equals K ​

leetcode 560. Subarray Sum Equals K

Intuition ​

Make nums a array that nums[i] = sum of nums[0] to nums[i], so we can access subarray sum with constant time. For instance, access sum from i to j, we can simply use nums[j] - nums[i-1].

So, we use a hashmap to store value that has been looped before, and because of IFF target == nums[j] - nums[i-1], we can add it to the result. Therefore nums[j] - target is the key to find.

Code ​

int subarraySum(vector<int>& nums, int k) {
    for(int i = 1; i < nums.size(); i++) {
        nums[i] += nums[i-1];
    }


    int res = 0;
    unordered_map<int,int>mp;
    mp[0]++;
    for(int i = 0; i < nums.size(); i++) {
        int target = nums[i] - k;
        if(mp.find(target) != end(mp))
            res += mp[target];
        mp[nums[i]]++;
    }

    return res;
}

Complexity Analysis ​

Time: O(n*log(n))

Space: O(n)