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

Challenge O(nlogn) time

Key Points: O(nlgn) O(n)

1. Sort the prefix sum
2. For each f(i), check f(i-1) -- it's the same as check f(i-1) and f(i+1) for f(i).

Java solution:

 public int[] subarraySumClosest(int[] nums) {
        if(nums.length==0){return null;}

        int len = nums.length, sum = 0, min = Integer.MAX_VALUE;
        int[] result = new int[2];
        Point[] points = new Point[len+1];

        points[0] = new Point(-1,0);
        for(int i=0; i<len; i++){
            sum += nums[i];
            points[i+1] = new Point(i,sum);
        }

        Arrays.sort(points,new Comparator<Point>(){
            @Override
            public int compare(Point a,Point b){
                return a.val-b.val;
            }
        });

        for(int i=1; i<points.length; i++){
            int temp = Math.abs(points[i].val-points[i-1].val);
            if(temp<=min){
                min = temp;
                result[0] = points[i].pos;
                result[1] = points[i-1].pos;
            }
        }

        Arrays.sort(result);
        result[0] = result[0]+1;
        return result;
    }

    class Point{
        int pos;
        int val;
        Point(int pos, int val){
            this.pos = pos;
            this.val = val;
        }
    }

C++ solution:

class Solution {
public:
    /**
     * @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
     */

    struct node {
        node(int _value, int _pos):value(_value), pos(_pos) {}
        int value, pos;

        // sort use < operator
        bool operator<(const node &o) const{
            return (value < o.value || value == o.value && pos < o.pos);
        }
    };

    vector<int> subarraySumClosest(vector<int> nums){
        // write your code here
        vector<int> results(2);

        vector<node> pre_sums;
        pre_sums.push_back(node(0,-1));

        int sum = 0;
        int len = nums.size();

        // 记录每一点的前缀和 "sum" 和 该点的坐标 "i"
        for (int i = 0; i < len ; ++i) {
            sum += nums[i];     
            pre_sums.push_back(node(sum, i));
        }

        // 对 pre_sums 排序
        sort(pre_sums.begin(), pre_sums.end());

        //  遍历所有点，找出点 i，满足 pre_sums[i] 与 pre_sums[i+1] 值最接近 
        len = pre_sums.size();
        int ans = INT_MAX; // 0x7fffffff;
        for (int i = 0; i < len-1; ++i){
            if (abs(pre_sums[i+1].value - pre_sums[i].value) < ans) { 
                ans = abs(pre_sums[i+1].value - pre_sums[i].value);
                results[0] = min(pre_sums[i].pos, pre_sums[i+1].pos)+1;
                results[1] = max(pre_sums[i].pos, pre_sums[i+1].pos);
            }
        }
        return results;
    }
};