给你一个长度为 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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum-closest
int threeSumClosest(int* nums, int numsSize, int target){
int i,j,k;
int MIN = 20001;
int sum;
int ret;
for (i=0;i<numsSize-2;i++){
for(j=i+1;j<numsSize-1;j++){
for(k=j+1;k<numsSize;k++){
sum = nums[i]+nums[j]+nums[k];
if(abs(sum-target)<MIN){
MIN = abs(sum-target);
ret = sum;
}
}
}
}
return ret;
}
99 / 99 个通过测试用例
状态：超出时间限制
题解中同样三个for但不会timeout的解
int threeSumClosest(int* nums, int numsSize, int target){
int min_sum = nums[0] + nums[1] + nums[2];
for (int i=0; i<numsSize; i++) {
for (int j=i+1; j<numsSize; j++) {
for (int k=j+1; k<numsSize; k++) {
int sum = nums[i] + nums[j] + nums[k];
int diff = sum - target > 0 ? sum - target : target - sum; // abs
int min_diff = min_sum - target > 0 ? min_sum - target : target - min_sum; // abs
if (diff < min_diff) {
min_sum = sum;
}
}
}
}
return min_sum;
}
//链接：https://leetcode.cn/problems/3sum-closest/solution/ni-you-ni-de-shuang-zhi-zhen-wo-you-wo-d-shgu/
执行用时：1988 ms 在所有 C 提交中击败了5.06%的用户
通过测试用例：
99 / 99
另外一个用qsort和双指针的题解，qsort函数用法也是先写cmp，主要看双指针
int cmp(int *a,int *b){
return *a-*b;
}
int threeSumClosest(int* nums, int numsSize, int target){
int p;//差值
int fp;//p的绝对值
int re;//结果
int now=0,l,r;
int sum=0;
qsort(nums,numsSize,sizeof(int),cmp);//快排
int min=10000;
while(now<numsSize-2){//双指针，循环开始
sum=0;
l=now+1;
r=numsSize-1;
while(l<r){
sum=nums[now]+nums[l]+nums[r];//和
p=sum-target;//和与目标数的差值
if(p==0)
return sum;//如果和与目标值相同，直接返回该值
else if(p>0){//和小于目标值，右指针向左移 因为左边的数较小，能降低和的值
r--;
}
else{//左指针右移
l++;
}
fp=fabs(p);//差值的绝对值
if(fp<min){//如果该绝对值比最小的差值绝对值还小，则最小值绝对值设为该数
min=fp;
re=sum;//记录下此时的和
}
}
now++;
}
return re;
}
因为不需要返回三个数的具体位置，先用qsort排序之后，求和逼近过程和15. 三数之和类似