<p>Given an array of integers <code>nums</code> and an integer <code>k</code>, return <em>the total number of subarrays whose sum equals to</em> <code>k</code>.</p>

<p>A subarray is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [1,1,1], k = 2
<strong>Output:</strong> 2
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [1,2,3], k = 3
<strong>Output:</strong> 2
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>-10<sup>7</sup> &lt;= k &lt;= 10<sup>7</sup></code></li>
</ul>

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        vector<int>prefix(nums.size() + 1,0 );
        for (int i = 0; i < nums.size(); i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        int result =0;
        map<int,int>mp;
        
        mp.insert({prefix[0],1});
        
        for (int i = 1; i < prefix.size(); i++) {
            int currentElement = prefix[i];
            int req = currentElement - k;
            if (mp.find(req) != mp.end()) {
                    //If the set contains req
                result = result + mp[req];
                
            }

            if (mp.find(currentElement) != mp.end()) {
                mp[currentElement] = mp[currentElement] + 1;
            } else {
                mp.insert({currentElement, 1});
            }
        }
        return result;

    }
};
45513