題目
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).
解題之法
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int closest = nums[0] + nums[1] + nums[2];
int diff = abs(closest - target);
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; ++i) {
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
int newDiff = abs(sum - target);
if (diff > newDiff) {
diff = newDiff;
closest = sum;
}
if (sum < target) ++left;
else --right;
}
}
return closest;
}
};
分析
這道題讓我們求最接近給定值的三數(shù)之和，是在之前那道 3Sum 三數(shù)之和的基礎(chǔ)上又增加了些許難度到旦，那么這道題讓我們返回這個(gè)最接近于給定值的值旨巷，即我們要保證當(dāng)前三數(shù)和跟給定值之間的差的絕對(duì)值最小，所以我們需要定義一個(gè)變量diff用來記錄差的絕對(duì)值添忘，然后我們還是要先將數(shù)組排個(gè)序采呐，然后開始遍歷數(shù)組，思路跟那道三數(shù)之和很相似搁骑，都是先確定一個(gè)數(shù)斧吐，然后用兩個(gè)指針left和right來滑動(dòng)尋找另外兩個(gè)數(shù)又固，每確定兩個(gè)數(shù)，我們求出此三數(shù)之和煤率，然后算和給定值的差的絕對(duì)值存在newDiff中仰冠，然后和diff比較并更新diff和結(jié)果closest即可。
