Print all sub arrays with zero sum
import java.util.*;
public class SubArraysWithZeroSum {
public static void main(String args[]) {
SubArraysWithZeroSum zeroSum = new SubArraysWithZeroSum();
int[][] input = {
null,
{},
{0},
{1,0},
{1,-1},
{3,4,-7,3,1,3,1,-4,-2,-2},
{1,2,3,-4}
};
for(int i=0; i< input.length; i++) {
System.out.println("Input: " + Arrays.toString(input[i]) + ", Result: " );
zeroSum.printAll(input[i]);
}
}
private void printAll(int[] input) {
if(input == null || input.length == 0) {
System.out.println("No zero sum sub arrays");
return;
}
// <CurrentSum, Index>
Map<Integer,List<Integer>> sumIndexTracker = new HashMap<Integer, List<Integer>>();
// Adding 0 if the input starts with 0
insert(sumIndexTracker, 0, -1);
int currentSum = 0;
for(int i=0; i< input.length; i++) {
currentSum += input[i];
if(sumIndexTracker.containsKey(currentSum)) {
for(int index: sumIndexTracker.get(currentSum)) {
print(input, index+1, i);
}
}
insert(sumIndexTracker, currentSum, i);
}
}
private void insert(Map<Integer,List<Integer>> sumTracker, int sum, int index) {
if(!sumTracker.containsKey(sum)) {
sumTracker.put(sum, new ArrayList<>());
}
sumTracker.get(sum).add(index);
}
private void print(int[] input, int start, int end) {
System.out.print("[");
for(int i=start; i<=end; i++) {
System.out.print(input[i] + ",");
}
System.out.println("]");
}
}