138. Subarray Sum Given an integer array, find a subarray 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 subarray that it’s sum equals to zero.

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

Solutions


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 List<Integer> subarraySum(int[] nums) {
        // prefixSum O(n) solution
        // [0, -100, -99, -97, -100, -96]
        //    [-100,  1,   2,  -3,    4]
        List<Integer> ret = new ArrayList<>();
        Map<Integer, Integer> hm = new HashMap<>();
        hm.put(0, -1);
        int curSum = 0;
        for (int i = 0; i < nums.length; i++) {
            curSum += nums[i];
            if (hm.containsKey(curSum)) {
                ret.addAll(Arrays.asList(hm.get(curSum) + 1, i));
                return ret;
            }
            hm.put(curSum, i);
        }
        
        ret.addAll(Arrays.asList(-1, -1));
        return ret;
    }
    
    // O(n^2) solution
    public List<Integer> subarraySum(int[] nums) {
        // write your code here
        List<Integer> ret = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int curSum = nums[i];
            if (curSum == 0) {
                    ret.addAll(Arrays.asList(i, i));
                    return ret;
                }
            for (int j = i + 1; j < nums.length; j++) {
                curSum += nums[j];
                if (curSum == 0) {
                    ret.addAll(Arrays.asList(i, j));
                    return ret;
                }
            }
        }
        
        ret.addAll(Arrays.asList(-1, -1));
        return ret;
    }
}