[LintCode] 139 Subarray Sum Closest 解题报告

Description
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又想到prefixSum。
我们算出所有的prefixSum，排个序。维护一个最小值closest，遍历一下排好序的sortedSum数组，相邻的两个看一下差如果小于closest，就更新答案。



Code

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 = new int[2];
        if (nums == null || nums.length == 0) {
            return res;
        }
        
        if (nums.length == 1) {
            res[0] = 0;
            res[1] = 0;
            return res;
        }
        
        
        Pair[] prefixSum = new Pair[nums.length + 1];
        prefixSum[0] = new Pair(0, 0);
        for (int i = 1; i <= nums.length; i++) {
            prefixSum[i] = new Pair(prefixSum[i - 1].sum + nums[i - 1], i);
        }
        
        Pair[] sortedSum = prefixSum;
        Arrays.sort(sortedSum, new Comparator<Pair>() {
            public int compare(Pair x, Pair y) {
                return x.sum - y.sum;
            }
        });
        
        int closest = Integer.MAX_VALUE;
        for (int i = 1; i < sortedSum.length; i++) {
            if (sortedSum[i].sum - sortedSum[i - 1].sum < closest) {
                closest = sortedSum[i].sum - sortedSum[i - 1].sum;
                res[0] = sortedSum[i].index - 1;
                res[1] = sortedSum[i - 1].index - 1;
            }
        }
        
        Arrays.sort(res);
        res[0]++;
        return res;
    }
}