最接近的三数之和-Toy模板网

这篇具有很好参考价值的文章主要介绍了最接近的三数之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

输入：nums = [0,0,0], target = 1
输出：0

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104

思路：
这个题和上一个题的思路是一样的，无非就是多了一个特殊的条件只存在唯一解，同样，我们可以运用到一定两动的双指针法来解决，一边动left和right指针，一边检测nums[i]+nums[left]+nums[right]的值和target 的接近度，只要比best更接近就替换，同时，为了避免重复计算相同的三数，对i和left，right我们一样要用到去重的操作，特殊的一点，我们在遇到三数之和刚好等于target的时候我们要直接返回target，因为没有比target更接近的数字了。

代码实现：文章来源地址https://www.toymoban.com/news/detail-719092.html

int cmp(const void* a, const void* b){
    return *((int*)a)>*((int*)b);
}
int threeSumClosest(int* nums, int numsSize, int target){
    int n=numsSize;
    if(n==3){
        return nums[0]+nums[1]+nums[2];
    }
    qsort(nums, n, sizeof(int), cmp);
    int best=1e7;
    for(int i=0; i<n-2; i++){
        if(i>0&&nums[i]==nums[i-1]){
            continue;
        }
        int left=i+1;
        int right=n-1;
        while(left<right){
            int sum=nums[i]+nums[left]+nums[right];
            if(sum==target){
                return target;
            }
            if(abs(sum-target)<abs(best-target)){
                best=sum;
            }
            if(sum<target){
                left++;
            }else{
                right--;
            }
        }
    }
    return best;
}

到了这里，关于最接近的三数之和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！