首页 > 试题广场 >

最接近的三数之和

[编程题]最接近的三数之和
  • 热度指数:1485 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个数组 nums 和一个目标值 target ,请问从 nums 中选出三个数,使其之和尽量接近目标数,即三数之和与目标数只差绝对值尽可能小。

返回满足题面要求的三数之和。

数据范围:数组长度满足 ,数组中的值满足 ,目标值满足 ,可以保证只有一个结果。
示例1

输入

[-1,2,1,-4],1

输出

2

说明

最接近 1 的三数之和是 -1+2+1 = 2  
示例2

输入

[0,0,0],1

输出

0

说明

 只有一种选择 0+0+0  
示例3

输入

[0,1,0,0],0

输出

0
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @param target int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */
#include<math.h>
int cmp(const void*a,const void*b){
    return(*(int*)a)-(*(int*)b);
}
int ClosestSum(int* nums, int numsLen, int target ) {
qsort(nums,numsLen,sizeof(nums[0]),cmp);
int i,j,k,sum,res;  

res=nums[0]+nums[1]+nums[2];

    for(i=0;i<numsLen;i++){
        j=i+1;
        k=numsLen-1;
        
      
        while(j<k){
              sum=nums[i]+nums[j]+nums[k];
            if(abs(sum-target)<abs(res-target)){
                res=sum;
            }
            if(sum>target){
                k--;
            }
            if(sum<target){
                j++;
            }
            if(sum==target){
                return sum;
            }
        }
     }
    return res;
}

发表于 2022-08-10 23:24:08 回复(0)