Subarray Sum Closest

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

------------------ thinking ------------------------
http://www.cnblogs.com/lishiblog/p/4187961.html
[INT_MAX]
----------------- codes ---------------------------

struct my_pair {
    int sum;
    int index;
    my_pair(int s, int i): sum(s), index(i) {}
};
bool myfunction(my_pair i, my_pair j) {return i.sum < j.sum;}
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){
        // write your code here
        vector<my_pair> arr;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            my_pair pair(sum, i);
            arr.push_back(pair);
        }
        my_pair pair(0, -1);
        arr.push_back(pair);
        sort(arr.begin(), arr.end(), myfunction);
        unsigned int diff = INT_MAX;
        vector<int> result(2, 0);
        for (int i = 0; i < arr.size() - 1; i++) {
            if (diff >= abs(arr[i].sum - arr[i+1].sum)) {
                diff = abs(arr[i].sum - arr[i+1].sum);
                result[0] = arr[i].index;
                result[1] = arr[i+1].index;
            }
        }
        sort(result.begin(), result.end());
        result[0] += 1;
        return result;
    }
};