Lintcode 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.

Example

Example 1:
 Input:  [-3, 1, 2, -3, 4]
 Output: [0, 2] or [1, 3].
 
 Explanation:
 return anyone that the sum is 0.

Example 2:
 Input:  [-3, 1, -4, 2, -3, 4]
 Output: [1,5]
 

Notice

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

Solution:
A[i] + ... a[j] = presum[j] - presum[i - 1]. This question requires the sum equals to zero, which means presum[j] = presum[i - 1]. It's like the two sum problem, we can use a hash table to store the previous presum[i - 1] and its index. 

Code (Java):

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) {
        List<Integer> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        int sum = 0;
        for (int i = 1; i <= nums.length; i++) {
            sum += nums[i - 1];
            if (map.containsKey(sum)) {
                ans.add(map.get(sum));
                ans.add(i - 1);
                break;
            } else {
                map.put(sum, i);
            }
        }
        
        return ans;
    }
}