Subarray Sum

Problem:

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.

2/23/2018 update

It has been explained pretty well below. But still need to note that, the prefix sum stores in hashtable instead of array. Initial the hashtable with (0, -1) is important. The case[1, -1] would not pass without (0, -1) pushed. Since it can not find the index before 0.

Solution:

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

------------------------------------------------------------------------------------------------------------------------

思路：
根据sub array sum公式 sum(i,j) = prefixsum(j+1) - prefixsum(i), subarray sum等于0, 那么prefix(j+1) = prefixsum(i)。把遍历数组过程中取得的prefix sum放在hashmap中，如果hashmap.contains(currentsum), 则得到答案。

假如在index为i的时候发现hashmap.contains(sum), 那么答案初始下标就是hashmap.get(sum)+1。因为prefixsum(i)对应的index是i-1。而所需要的范围是i-j。nums[i-1] is exclusive, nums[j] is inclusive.

prefixsum[0] =  0：这样就可以把数组第一个元素考虑进去。