-
-
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; | |
} | |
}; |
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;
please provide code for python
@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.
the solution is not working