Given an integer array, find a subarray where the sum of numbers iszero. Your code should return the index of the first number and the index of the last number.

Notice

There is at least one subarray that it's sum equals to zero.

Have you met this question in a real interview?

Yes

Example

Given[-3, 1, 2, -3, 4], return[0, 2]or[1, 3].

1. brute force

public ArrayList<Integer> subarraySum(int[] nums) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                result.add(i);
                result.add(i);
                return result;
            }
            int sum = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                sum = sum + nums[j];
                if (sum == 0) {
                    result.add(i);
                    result.add(j);
                    return result;
                }
            }
        }
        return result;
    }

2. public ArrayList<Integer> subarraySum(int[] nums) {
        ArrayList<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        HashMap<Integer, Integer> memo = new HashMap<>();
        memo.put(0, -1);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = sum + nums[i];
            if (memo.containsKey(sum)) {
                result.add(memo.get(sum) + 1);
                result.add(i);
                return result;
            }
            memo.put(sum, i);
        }
        return result;
    }
   

3.

class Pair {
    int value;
    int index;
    public Pair(int value, int index) {
        this.value = value;
        this.index = index;
    }
}

public ArrayList<Integer> subarraySum(int[] nums) {
        ArrayList<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        Pair[] sum = new Pair[nums.length + 1];
        sum[0] = new Pair(0, 0);
        int prev = 0;
        for (int i = 1; i < sum.length; i++) {
            if (nums[i - 1] + prev == 0) {
                result.add(0);
                result.add(i - 1);
                return result;
            }
            sum[i] = new Pair(nums[i - 1] + prev, i);
            prev = sum[i].value;
        }
        Arrays.sort(sum, new Comparator<Pair>(){
            public int compare(Pair a, Pair b) {
                return a.value - b.value;
            }
        });
        for (int i = 1; i < sum.length; i++) {
            if (sum[i].value == sum[i - 1].value) {
                result.add(Math.min(sum[i].index - 1 , sum[i - 1].index - 1) + 1);
                result.add(Math.max(sum[i].index - 1, sum[i - 1].index - 1));
                return result;
            }
        }
        return result;


    }