schintan22
BAN USERimport java.util.HashMap;
class SumSubarrayCount {
// Counts the number of subarrays with sero sum
static int countZeroSumSubarrays(int arr[],int low,int high)
{
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
// Initialize sum of elements
int sum = 0;
for (int i = 0; i < arr.length; i++)
{
if(arr[i]>=low && arr[i]<=high)
hM.put(arr[i],0);
}
//Counter of subarrays
int count = 0;
// Traverse through the given array
for (int i = 0; i < arr.length; i++)
{
//Calculate new sum
sum += arr[i];
if (hM.containsKey(sum)){
if(arr[i]>=low && arr[i]<=high)
{
hM.put(sum, hM.get(sum) + 1);
count += hM.get(sum);
}
} else{
// If the sum has not been seen, we initialize its key.
hM.put(sum,0);
}
}
return count;
}
}
Please check below working java solution O(MN) time complexity and O(1) space complexity.
- schintan22 March 30, 2017