Subarray Sum Closest

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

Thoughts

我们可以采用和subarray sum相同的方法，但由于不知道与当前sum最相近的值是多少，我们还是需要遍历前面的元素，也就是$O(n^2)$. 有没有办法能快速找到ｉ之前与sum[i]最相近的？我们需要找到与sum[i]的相近元素的相对位置，所以想到对sum[]先排序。

由于需要返回下标，所以用一个特殊的类来存储sums.

Code

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) {
        int n = nums.length;
        SumElement[] sums = new SumElement[n];

        for (int i = 0, sum = 0; i < n; i++) {
            sum += nums[i];
            sums[i] = new SumElement(sum, i);
        }

        Arrays.sort(sums, new SumElementComparator());
        int min = Integer.MAX_VALUE;
        int[] res = new int[2];
        for (int i = 1; i < n; i++) {
            if (sums[i].sum - sums[i - 1].sum < min) {
                if (sums[i - 1].index < sums[i].index) {
                    res[0] = sums[i - 1].index + 1;
                    res[1] = sums[i].index;
                } else {
                    res[0] = sums[i].index + 1;
                    res[1] = sums[i - 1].index;
                }
                min = sums[i].sum - sums[i - 1].sum;
            } 
        }

        return res;
    }

    class SumElement {
        int sum;
        int index;
        SumElement(int sum, int index) {
            this.sum = sum;
            this.index = index;
        }
    }

    class SumElementComparator implements Comparator<SumElement> {
        public int compare(SumElement a, SumElement b) {
            return a.sum - b.sum;
        }
    }

}

Analysis

TC: O(nlgn) due to sorting. SC: O(n)