Online Judge Solutions

Sunday, December 14, 2014

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

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){
        MySet sumSet;
        int cumuSum = 0;
        int minDist = INT_MAX;
        vector<int> ret(2);
        
        sumSet.insert(make_pair(0, -1));
        for(int i = 0; i < nums.size(); i++) {
            if (abs(nums[i]) < minDist) {
                minDist = abs(nums[i]);
                ret[0] = i;
                ret[1] = i;
            }
            
            cumuSum += nums[i];
            
            // set::lower_bound(e) returns a iterator pointing to a elements in
            // the set that is equal or greator than e.
            // here, we set pair::second to be 0 so that, if there was a same cumuSum
            // appear before, lower_bound will return iterator to that elments. 
            MySet::iterator lower = sumSet.lower_bound(make_pair(cumuSum, 0));
            
            // Check the two of the previous cumulative sums around cumuSum
            // one less than and the other greater than
            for(int k = 0; k < 2; k++) {
                if (lower != sumSet.end()) {
                    int dist = abs(lower->first - cumuSum);
                    if (dist < minDist){
                        minDist = dist;
                        ret[0] = lower->second + 1;
                        ret[1] = i;
                    } 
                
                    if (dist == 0)
                        break;
                }
            
                lower--;
            } 
            
            sumSet.insert(make_pair(cumuSum, i));
        }
         
        return ret;
    }
};

No comments:

Post a Comment