1
class Solution {
2
 public:
3
  int subarraySum(vector<int> &arr, int k) {
4
    int n = arr.size(); // take the size of the array
5

6
    int prefix[n]; // make a prefix array to store prefix sum
7

8
    prefix[0] = arr[0]; // for element at index at zero, it is same
9

10
    // making our prefix array
11
    for (int i = 1; i < n; i++) {
12
      prefix[i] = arr[i] + prefix[i - 1];
13
    }
14

15
    unordered_map<int, int> mp; // declare an unordered map
16

17
    int ans = 0; // to store the number of our subarrays having sum as 'k'
18

19
    for (int i = 0; i < n; i++) // traverse from the prefix array
20
    {
21
      if (prefix[i] == k) // if it already becomes equal to k, then increment ans
22
        ans++;
23

24
      // now, as we discussed find whether (prefix[i] - k) present in map or not
25
      if (mp.find(prefix[i] - k) != mp.end()) {
26
        ans += mp[prefix[i] - k]; // if yes, then add it our answer
27
      }
28

29
      mp[prefix[i]]++; // put prefix sum into our map
30
    }
31

32
    return ans; // and at last, return our answer
33
  }
34
};