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.

http://www.lintcode.com/en/problem/subarray-sum-closest/

Discussion

用数组sum[i]记录0~i的和，同时记录下index i（用pair），对sum排序，则相邻的sum[i]（对应index m）-sum[i-1]（对应index n）则表示m+1~n的和 （假设m<n),记录最接近0 的，输出{m+1, n}.

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
     */
    vector<int> subarraySumClosest(vector<int> nums){
        vector<int> result(2,0);
        if(nums.empty()) return result;
        //1. save the accumulated sum and according index
        int n = nums.size();
        vector<pair<int, int> > sums;
        sums.emplace_back(make_pair(nums[0], 0));
        for(int i=1; i<n; i++) {
            //sums[i] = sums[i-1] + nums[i];
            int tmp = sums.back().first + nums[i];
            sums.emplace_back(make_pair(tmp, i));
        }
        //2. sort sums, saving the index information for next comutation
        sort(sums.begin(), sums.end());
        //3. find the closest sum to zero
        int minDiff = INT_MAX;
        for(int i=1; i<n; i++) {
            int diff = abs(sums[i].first - sums[i-1].first);
            if(diff < minDiff) {
                minDiff = diff;
                result[0] = min(sums[i-1].second, sums[i].second) + 1;
                result[1] = max(sums[i-1].second, sums[i].second);
            }
        }
        return result;
    }
};