Created
April 22, 2020 14:30
-
-
Save SuryaPratapK/cc99cf19e8d65a96525ee1c87d3e75c7 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
}; |
@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
please provide code for python