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