16 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
- The idea with this one follows the same strategy as 15 3Sum (explanation is in there). The only difference now is that we are iterating towards a target value. Because we're dealing with how close the values are - the difference between the sum and the target value will give us the solution.
- So to do this, I've maintained the minimum difference using a priority queue that pairs with the actual sum. Then I just return the top of the queue.
- But I could have just as easily maintained the minimum within the algorithm in O(1) and O(1) space using a simple check.
typedef pair<int, int> P;
struct Order {
bool operator()(P const& a, P const& b) const {
return a.first > b.first;
//return a.second < b.second || a.second == b.second && a.first < b.first;
}
};
int threeSumClosest(vector<int>& nums, int target) {
if (nums.size() < 3) return 0;
priority_queue< P, vector<P>, Order> pq;
sort(nums.begin(), nums.end());
int cur_sum;
int main, iter, max;
for (int main = 1; main <= nums.size(); main++) {
iter = main + 1;
max = nums.size() - 1;
while (max >= iter) {
//cout << nums.at(main - 1) << " " << nums.at(iter - 1) << " " << nums.at(max) << endl;
cur_sum = nums.at(main - 1) + nums.at(iter - 1) + nums.at(max);
// as close as you can get
if (cur_sum == target)
return cur_sum;
else if (cur_sum < target)
iter++;
else // cur_sum > target
max--;
pq.push(make_pair(abs(cur_sum - target), cur_sum));
}
}
return pq.top().second;
}
int main() {
vector<int> nums = { 1,2,4,8,16,32,64,128 };
cout << threeSumClosest(nums, 82) << endl;
pause();
nums = { -10, 3, 3, -90, 100, 3, 4, 5 };
cout << threeSumClosest(nums, 1) << endl;
pause();
}
Last modified 3yr ago