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.

分析：

这题目挺难得，需要operator overloading。还不容易想到用subarray sum可以做O(nlogn)。

最原始的想法肯定是用O(n^2)算出所有subarray的值，然后记录最小。然后考官就会问，你怎么优化一下？这时候拿出O(n)的subarray sum然后做O(nlogn)的排序解决。

解法：

class sumIndexPair {
public:    
    int sum;
    int index;
    sumIndexPair(int _sum, int _index) : sum(_sum), index(_index) {}
    bool operator < (const sumIndexPair &rhs) const {
        return (sum < rhs.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
        if (nums.size() == 0) {
            return vector<int>();
        }
        if (nums.size() == 1) {
            return vector<int>(nums[0]);
        }
        vector<sumIndexPair> Hash;
        Hash.push_back(sumIndexPair(0, -1) );
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            Hash.push_back(sumIndexPair(sum, i) );
        }
        sort(Hash.begin(), Hash.end() );
        int minSum = INT_MAX;
        vector<int> res = {-1, -1};
        for (int i = 1; i < nums.size(); i++) {
            int temp = abs(Hash[i - 1].sum - Hash[i].sum);
            if (temp < minSum) {
                minSum = temp;
                res[0] = min(Hash[i - 1].index, Hash[i].index) + 1;
                res[1] = max(Hash[i - 1].index, Hash[i].index);
            }
        }
        return res;
    }
};