Subarray Sum Closest

Source

• lintcode: Subarray Sum Closest

Given an integer array, find a subarray with sumclosest 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

题解

1. 首先遍历一次数组求得子串和。
2. 对子串和排序。
3. 逐个比较相邻两项差值的绝对值，返回差值绝对值最小的两项。

Java

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 s, int i) {
            sum = s;
            index = i;
        }
    }
    public int[] subarraySumClosest(int[] nums) {
        // write your code here
        int[] res = new int[2];
        int len = nums.length;
        if (nums == null || len == 0 || len==1) {
            return res;
        } 

        Pair[] sums = new Pair[len+1];
        sums[0] = new Pair(0, 0);
        int current_sum=0;
        for (int i = 1; i <= len; i++) {
            current_sum+=nums[i-1];
            sums[i] = new Pair(current_sum, i);
        }

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

        int[] tmp = new int[2];
        int closet = Integer.MAX_VALUE;
        for (int i = 1; i <= len; i++) {

            if (closet > sums[i].sum - sums[i-1].sum) {
                closet = sums[i].sum - sums[i-1].sum;

                tmp = new int[]{sums[i].index, sums[i - 1].index};

                Arrays.sort(tmp);
                res[0] = tmp[0] ;
                res[1] = tmp[1]-1;
            }
        }

        return res;
    }
}