Note:

This problem states that – Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k.

Brute force method: It comes to the mind easily. Time complexity is O(n^2) and space complexity is O(1). So in most cases, this solution would exceed the time limit.

int subarraySum(vector<int>& nums, int k) {
        int ans=0;
        for(int i=0; i<nums.size(); i++)
        {
            int total=0;
            for(int j=i; j<nums.size(); j++)
            {
                total+=nums[j];
                if(total==k) ans++;
            }
        }
        return ans;    
    }

Cumulative /Prefix Sum:

Though this thing doesn’t come to mind at first, this way is the more efficient one. The main trick is we have to keep the cumulative sum in an array first, then we’ll have to work on that array. The first idea is that to know the sum of any subarray in the range [i,j], the equation would be: sum=a[j]-a[i-1] (assuming a is the cumulative sum array). Since our sum has to be k, so we can write, k=a[j]-a[i-1]. Alternatively, we can write, a[i-1]=a[j]-k. Now we will have to run a loop for each j, to see whether there is any prefix sum equal to a[i-1] till now. We’ll check that with the help of a hashmap. If our condition is satisfied, we increase our answer variable by the count in the hashmap.

Time complexity: O(N)
Space complexity: O(N); for the hashmap.

int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> ump;
        ump[0]=1;
        int a[20004]={0};
        int ans=0;
        for(int i=0; i<nums.size(); i++)
        {
            if(i==0) a[i]=nums[i];
            else a[i]=a[i-1]+nums[i];
            
            int x=a[i]-k;
            if(ump.count(x)) ans+=ump[x];
            ump[a[i]]++;
        }
        return ans;    
    }