Subarray Sum Closest

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

Solution:

We calculate the prefix sum first and stored each prefix sum with its index (0, index). Sort all the prefix according to their sum values. Then, find the smallest difference between neighboring prefix sums in sorted list. The indices between these two prefix sums are the final result.

Code:

class Prefix implements Comparable<Prefix> {
    int sum;
    int idx;
    Prefix(int inSum, int inIdx) {
        sum = inSum;
        idx = inIdx;
    }
    @Override public int compareTo(Prefix that) {
        return this.sum - that.sum;
    }
}

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) {
        if (nums == null || nums.length == 0) {
            return new int[] {-1, -1};
        }
        if (nums.length == 1) {
            return new int[] {0, 0};
        }
        Prefix[] prefix = new Prefix[nums.length + 1];
        int sum = 0;
        prefix[0] = new Prefix(sum, 0);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            prefix[i + 1] = new Prefix(sum, i + 1);
        }
        Arrays.sort(prefix);
        int best = Integer.MAX_VALUE;
        int[] result = new int[2];
        for (int i = 1; i < prefix.length; i++) {
            if (best > prefix[i].sum - prefix[i - 1].sum) {
                best = prefix[i].sum - prefix[i - 1].sum;
                result[0] = prefix[i].idx - 1;
                result[1] = prefix[i - 1].idx - 1;
            }
        }
        Arrays.sort(result);
        result[0]++;
        return result;
    }
}