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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

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;     } }