Wednesday, June 18, 2014

Find if there is a subarray with 0 sum



// Print starting and ending indexes of all subarrays with 0 sum.

static boolean isExistSumZero(int[] arr){
int len = arr.length;

if(len == 0) return false;
int sum = 0, start=0, end=0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i< len; i++)
{
sum += arr[i];

if(arr[i] == 0 || sum == 0 || map.get(sum) != null)
{
if(map.get(sum) != null)
start = map.get(sum)+1;
else if(arr[i] == 0) start = i;
else start = 0;
end = i;
System.out.println(start +","+ end);
return true;
}

map.put(sum, i);
}
return false;
}

References:
http://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/

No comments:

Post a Comment