最接近的三数之和

最接近的三数之和 题目描述：

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

返回这三个数的和。

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

示例：

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

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

解答描述：

该题要找到三数和与target最接近的三元组，和上一题三数之和非常之相似，但要简单一些。

同样地，为了后续指针遍历方便，先对数组进行qsort快排进行升序排序。

然后，同样地，遵循先固定a，再寻找b，c的思想，且在寻找b，c的过程中，为了降低时间复杂度，采用双指针法，定义两个指针，分别为l=i+1,r=numSize-1:则nums[i]=a,nums[l]=b,nums[r]=c;

1)当d=a+b+c-target>0时，说明需要减小值，则r--；

2)当d=a+b+c-target<0时，说明需要增大值，则l++；

3)当a+b+c=0时，说明找到了一个和刚好等于target的三元组，必然是最接近target的，直接返回target即可。
在遍历过程中，采用变量min_dis记录当前的三数和和target的距离，且在过程中更新。

代码：

int comp(const void*a,const void*b)//比较函数
{
    return *(int*)a-*(int*)b;
}
int abs(int x)
{
    return x>=0?x:x*(-1);
}
int threeSumClosest(int* nums, int numsSize, int target){
    qsort(nums,numsSize,sizeof(int),comp);//排序
    int min_dis=10000;//三数和和target的距离
    int sum=0;//最接近target的和
    for(int i=0;i0)//三数和比target大
            {
                r--;
                if(abs(d) 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5711560.html