Subarray Sum Closest

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

Challenge O(nlogn) time

注意 与subarray sum对比来看。我们都是加入了一个-1的point来辅助运算。另外注意两个和的差值之间，本身在数组index比较小的是前一个prefixsum， 所以是start， 然后index都是index+1，大的那一个是结束点，index是本身

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
     */
    class Pair {
        int sum;
        int index;
        public Pair(int sum, int index) {
            this.sum = sum;
            this.index = index;
        }
    }
    public int[] subarraySumClosest(int[] nums) {
        // write your code here
        int[] res = new int[2];
        if (nums == null || nums.length == 0) return res;
        Pair[] pairs = new Pair[nums.length + 1];
        int sum = 0;
        pairs[0] = new Pair(0, -1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            pairs[i + 1] = new Pair(sum, i);
        }
        Arrays.sort(pairs, new Comparator<Pair>(){
            public int compare(Pair a, Pair b) {
                if (a.sum  == b.sum) {
                    return a.index - b.index;
                }
                return a.sum - b.sum;
            }
        });
        int minValue = Integer.MAX_VALUE;

        for (int i = 1; i < pairs.length; i++) {
            int curDiff = Math.abs(pairs[i].sum - pairs[i-1].sum);
            if (curDiff <= minValue) {
                minValue = curDiff;
                res[0] = Math.min(pairs[i-1].index, pairs[i].index) + 1;
                res[1] = Math.max(pairs[i-1].index, pairs[i].index);
            }
        }
        return res;
    }
}