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.

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

思路

• naive solution
  • loop through the array, every time we stands at an element, we go back to see its previous elements and sum them up to see if result is zero.
  • time complexity
    • O(n^2)
• optimization
  • there is duplicate computation
  • when going through this array, assume the pointer is standing at 2, we can get the sum from the beginning to 2. when we move the pointer forward to -3, we would get the sum from the beginning to -3. so if we store all the prefix sum in a hashtable, and when looping through the array, we find if there is a prefix sum equal to current sum. If it does, we got the answer.

• 

• 注意两个重要点:

  • edge case:
    • [0]
    • [1,-1]
    • so we need to add (0, -1) to the map.

    public ArrayList<Integer> subarraySum(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<Integer>();
        }

        Map<Integer, Integer> map = new HashMap<>();
        // 这一步很重要
        map.put(0, -1);

        int sum = 0;
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum)) {
                // 需要 + 1
                res.add(map.get(sum) + 1);
                res.add(i);
                break;
            }
            map.put(sum, i);
        }

        return res;
    }