Subarray Sum Closet

题目：

Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.

分析：

这题目需要用到自定义的数据结构，及其排序

解法：

class Pair {
    int sum;
    int index;
    public Pair(int sum, int index) {
        this.sum = sum;
        this.index = 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
     */
    public int[] subarraySumClosest(int[] nums) {
        // write your code here
        int[] res = {-1, -1};
        if (nums.length == 0) {
            return res;
        }
        if (nums.length == 1) {
            res[0] = 0;
            res[1] = 0;
            return res;
        }

        Pair[] subSum = new Pair[nums.length + 1];
        subSum[0] = new Pair(0, 0);
        int sum = 0;

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            subSum[i + 1] = new Pair(sum, i + 1);
        }

        Arrays.sort(subSum, new Comparator<Pair>() {
            public int compare(Pair a, Pair b) {
                return a.sum - b.sum;
            }
        });

        int minSum = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (minSum > subSum[i + 1].sum - subSum[i].sum) {
                minSum = subSum[i + 1].sum - subSum[i].sum;
                int[] temp = new int[]{subSum[i].index - 1, subSum[i + 1].index - 1};
                Arrays.sort(temp);
                res[0] = temp[0] + 1;
                res[1] = temp[1];
            }
        }
        return res;
    }
}