LeetCode 16. 最接近的三数之和
原题链接
中等
作者:
ShineShaye
,
2022-07-04 10:26:56
,
所有人可见
,
阅读 99
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
// 这题存储有点搞,要求三个数加和与目标值最接近,返回的是三个数的和
// 为了比较每次加和和target的差值,必须存储这个差值
// 同时为了范围三个数的和,必须存储该加和
// 需要用一个pair来存储
pair<int, int> res = {INT_MAX, 0};
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size() - 2; ++i)
{
if(i && nums[i] == nums[i - 1]) continue;
for(int j = i + 1, k = nums.size() - 1; j < k; ++j)
{
if(j > i + 1 && nums[j] == nums[j - 1]) continue;
while(j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= target) --k;
int add = nums[i] + nums[j] + nums[k];
if(res.first > abs(add - target))
res = {abs(add - target), add};
add = nums[i] + nums[j] + nums[k - 1];
if(k - 1 > j && res.first > target - add)
res = {target - add, add};
}
}
return res.second;
}
};