560. Subarray Sum Equals K

Problem Statement

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= nums.length <= 2 * 104

• -1000 <= nums[i] <= 1000

• -107 <= k <= 107

Intuition

Approach:

The thing is we maintain a prefix sum kind to track the subarrays

eg
1 2 3 arr
1 3 6 pre

Let k=3 sum required

Now
1 2 3
1 3 6

We can see that
)1 2) 3
This gives us the sum 
also

1 2 ) 3 )
this gives 

Also store the sum in map regularly 
Edge case

1) 0) 1 0 1
1  1  2 2 3
Hence we keep track of such 1->2 and then when we encounter 3 - 2 = 1
We take ones count = 2 and add to ans
Sum = 2
1

Links

https://leetcode.com/problems/subarray-sum-equals-k/description/

Video Links

Approach 1:

C++

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        int sum=0, ans=0;
        mp[0] = 1;

        for(int i=0; i<nums.size(); i++){
            sum += nums[i];
            
            if(mp[sum-k]){
                ans += mp[sum-k];
            }

            mp[sum]++;
        }

        return ans;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems