Problem

Given an integer array, find a subarray with sum closest to zero. 

Return the indexes of the first number and last number.

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

思路

• 不能沿用subarray sum的hashmap做法
• 暴力解法:
  • 遍历prefix sum数组的元素的时候, 当前前缀和与它前面的前缀和相减, 更新最小差值以及其索引
• 优化:
  • 因为我们找的是最小差值, 换句话说只需要与数值最接近的前缀和相减即可, 所以将前缀和以及其索引排序.
  • 排序后遍历一遍求出最小差值
• 

    public int[] subarraySumClosest(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        } 
        int len = nums.length;
        Pair[] pairs = new Pair[len + 1];

        pairs[0] = new Pair(0, 0);
        for (int i = 1; i <= len; i++) {
            pairs[i] = new Pair(pairs[i - 1].sum + nums[i - 1], i);
            // System.out.println(pairs[i].sum);
        }


        Arrays.sort(pairs, new Comparator<Pair>() {
            public int compare(Pair p1, Pair p2) {
                return p1.sum - p2.sum;
            }
        });

        int min = Integer.MAX_VALUE;
        int[] ans = new int[2];

        for (int i = len; i >= 1; i--) {
            Pair p1 = pairs[i];
            Pair p2 = pairs[i - 1];
            int dif = Math.abs(p1.sum - p2.sum);
            if (min > dif) {
                min = dif;
                ans[0] = Math.min(p1.index, p2.index);
                ans[1] = Math.max(p1.index, p2.index) - 1;
            }
        }

        return ans;
    }

    class Pair {
        int sum;
        int index;

        public Pair (int sum, int index) {
            this.sum = sum;
            this.index = index;
        }
    }