題目鏈接
tag:
- Medium
- Two Pointers
question:
??Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
Example1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Example2:
Input: nums = [0,0,0], target = 1
Output: 0
Constraints:
- -3 <= nums.length <= 1000
- -1000 <= nums[i] <= 1000
- -104 <= target <= 104
思路：
??這道題讓求最接近給定值的三數(shù)之和，是在之前那道 3Sum 的基礎(chǔ)上又增加了些難度，那么這道題讓返回這個(gè)最接近于給定值的值登渣，即要保證當(dāng)前三數(shù)和跟給定值之間的差的絕對(duì)值最小，所以需要定義一個(gè)變量 diff 用來(lái)記錄差的絕對(duì)值悯搔，然后還是要先將數(shù)組排個(gè)序蝉仇，然后開始遍歷數(shù)組惠遏，思路跟那道三數(shù)之和很相似机打，都是先確定一個(gè)數(shù)蓬坡，然后用兩個(gè)指針 left 和 right 來(lái)滑動(dòng)尋找另外兩個(gè)數(shù)猿棉，每確定兩個(gè)數(shù)磅叛，求出此三數(shù)之和，然后算和給定值的差的絕對(duì)值存在 newDiff 中萨赁，然后和 diff 比較并更新 diff 和結(jié)果 closest 即可弊琴，其實(shí)還可以稍稍進(jìn)行一下優(yōu)化，遍歷時(shí)每次判斷一下杖爽，當(dāng) nums[i]*3 > target 的時(shí)候敲董，就可以直接比較 closest 和 nums[i] + nums[i+1] + nums[i+2] 的值，返回較小的那個(gè)慰安，因?yàn)閿?shù)組已經(jīng)排過(guò)序了腋寨，后面的數(shù)字只會(huì)越來(lái)越大，就不必再往后比較了化焕，代碼如下：
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
// 快排+雙指針
int closest = nums[0] + nums[1] + nums[2];
sort(nums.begin(), nums.end());
int diff = abs(target - closest);
for (int i = 0; i < nums.size() - 2; ++i) {
if (nums[i] * 3 > target) return min(closest, nums[i] + nums[i+1] + nums[i+2]);
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
int new_diff = abs(sum - target);
if (new_diff < diff) {
diff = new_diff;
closest = sum;
}
if (sum < target) ++left;
else --right;
}
}
return closest;
}
};
