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

思路一(循环)

• 遍历数组, 对当前元素, 遍历其前面所有元素
• 时间复杂度: O(n ^ 2)
• 空间复杂度: O(1)

思路二(hashMap + prefix sum)

• 优化思路:
  • 因为不能排序, 所以想到O(n)复杂度
  • 遍历数组, 对当前元素, 需要以O(1)的时间找到它前边存在过的相同的prefix sum,
  • 所以需要hashmap

    public ArrayList<Integer> subarraySum(int[] nums) {
        ArrayList<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum)) {
                res.add(map.get(sum) + 1);
                res.add(i);
                break;
            }
            map.put(sum, i);
        }
        return res;
    }