LintCode "Subarray Sum Closest"

O(nlgn) - my first thought is, keep maintaining a balanced binary search tree, and then use "Binary Search Tree Closest" one to solve it. But unfortunately there's no on-hand stl class for it. The closest one is multiset<T>. 

However, we don't have to use binary search tree. Since we are looking for closest partial sum - we can sort it, then check neighbor 2.

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)
    {
        if (nums.empty()) {
            return {};
        }

        const int n = nums.size();
        vector<pair<int, int>> psum(n + 1);

        // Get and Sort the partial sum. a little greedy
        for (int i = 0; i < n; ++i) {
            psum[i + 1].first = psum[i].first + nums[i];
            psum[i + 1].second = i + 1;
        }
        sort(psum.begin(), psum.end());

        int d = INT_MAX;
        int ri = 1;
        for (int i = 1; i < n + 1; ++i)
        {
           int curr = abs(psum[i].first - psum[i - 1].first);
           if (d > curr)
           {
                d = curr;
                ri = i;
            }
        }

        int l = min(psum[ri - 1].second, psum[ri].second);
        int r = -1 + max(psum[ri - 1].second, psum[ri].second);
        return {l, r};
    }
};