Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save SuryaPratapK/cc99cf19e8d65a96525ee1c87d3e75c7 to your computer and use it in GitHub Desktop.
Save SuryaPratapK/cc99cf19e8d65a96525ee1c87d3e75c7 to your computer and use it in GitHub Desktop.
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
//For fast I/O in C++
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n = nums.size();
if(n==0)
return 0;
unordered_map<int,int> mymap; //Key = PrefixSUM, Value = Count of PrefixSUM.
int currSUM = 0;
int i = 0;
int count = 0;
while(i<n)
{
currSUM += nums[i];
if(currSUM == k) //We found a new subArray with SUM = k
count += 1;
if(mymap.find(currSUM-k)!=mymap.end())
count += mymap[currSUM-k];
mymap[currSUM] += 1;
i += 1;
}
return count;
}
};
@akshit0699
Copy link

Could you please explain how this thing works:
//For fast I/O in C++
ios_base::sync_with_stdio(false);
cin.tie(NULL);

@RajeshKumar138
Copy link

the solution is not working

@praka07
Copy link

praka07 commented Apr 21, 2022

working

HashMap<Integer, Integer> map = new HashMap<>();
int count = 0;
int currentSum = 0;
int[] psa = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
currentSum += nums[i];
if (currentSum == k) {
count++;
}
if (map.containsKey(currentSum - k)) {
count += map.get(currentSum - k);
}
map.put(currentSum, map.getOrDefault(currentSum, 0) + 1);
}
return count;

@kairanishanth
Copy link

please provide code for python

@nikhilx144
Copy link

@praka07
the code to return the count/ number of subarrays with sum exactly equal to k is:

int i = 0, count = 0, currentSum = 0, n = arr.length;
HashMap<Integer, Integer> hm = new HashMap<>();
while (i < n) {
currentSum += arr[i];
i++;
if (currentSum == k || hm.containsKey(currentSum - k))
count ++;
hm.put(currentSum, hm.getOrDefault(currentSum, 0) + 1);
}
return count;

if (currentSum - k) is present in the hash map then it implies that there exists one subarray whose sum is equal to k from index 0 to i, therefore we increment count.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment