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
     
       subarraySumClosest(vector
      
        nums)    {        if (nums.empty()) {            return {};        }        const int n = nums.size();        vector
       
        
         > 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};    }};