1. 题目描述
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
2. 提交记录
16.最接近的三数之和
3. 算法思想
为了能够找出与 target 最接近的整数和，需要先对数组 nums 进行排序。
看到题目，我最先想到的是暴力解决，三层 for 循环,但是这种方法显然不是最好的，因为时间复杂度比较高O（n3）.之前在评论区看过双指针法，做了“三数之和”这道题，我真的是要实名夸赞这种解法，所以这次也毫不犹豫选择了双指针法。算法思想如下：
先给整数和sum赋一个初始值 sum = nums[0]+nums[1]+nums[2]；
在for循环中设置左指针 left = i+1 ； 右指针 right 指向数组最后一位 right = numsSize-1;
需要注意的是为了能够找出与 target 最接近的整数和，需要对每个整数和进行比较，选出最接近 target 的结果。
4. 代码实现
int threeSumClosest(int* nums, int numsSize, int target){
//从小到大排序
int temp = 0;
for(int i=0;i <= numsSize-2;i++){
for(int j=i+1;j <= numsSize-1;j++){
if(nums[i] > nums[j]){
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
//双指针
int left,right,sum = nums[0]+nums[1]+nums[2];
for(int i = 0;i< numsSize-2;i++){
left = i+1;
right = numsSize-1;
while(left < right){
temp = nums[i]+nums[left]+nums[right];
if(temp > target){
right--;
}else if(temp < target){
left++;
}else{
return temp;
}
if(fabs(temp-target) < fabs(sum-target)){
sum = temp;
}
}
}
return sum;
}
