Description

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

Notice

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

Example

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

Solution

i->j的sub array sum为0的变相条件为0->i-1和0->j的sub array sum相等。因此，用一个hashmap记录sub array sum和当前index即可，遇到相同的sub array sum就返回
要注意的是对于sub array sum为0的情况，可以直接返回0->当前index，因此要在map中加入初始情况(0, -1)

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number 
     *          and the index of the last number
     */
    public ArrayList<Integer> subarraySum(int[] nums) {
        // write your code here
        ArrayList<Integer> indices = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return indices;
        }

        int sum = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum)) {
                indices.add(map.get(sum) + 1);
                indices.add(i);
                return indices;
            } else {
                map.put(sum, i);
            }
        }

        return indices;
    }
}

.