题目
最接近的三数之和
https://leetcode-cn.com/problems/3sum-closest/
公众号 《java编程手记》记录JAVA学习日常，分享学习路上点点滴滴，从入门到放弃，欢迎关注
描述
难度：中等
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4
Solution
双指针解法
解题思路
题目条件
跟昨天写的三数之和差不多，唯一不同的点在于，三数之和是求出a+b+c=0的三个数，这题求得是a+b+c的值最接近target
暴力解法我就不过多讲解了，直接多重FOR循环遍历求值即可，找到小于当前最小值的就替换，但是 最终提交结果八成也是超时
还是使用双指针的方式
我们先将
nums进行从小到大的排序，对排序后的数组循环遍历，使用双指针分别指向当前
nums[i]的右侧和nums数组的最右侧-
计算
nums[i] + nums[left] +nums[right]的值-
nums[i] + nums[left] +nums[right] > target，当前总值大于target值 ，在上一步已经进行了由小到大的排序，则需要Right的指针左移 -
nums[i] + nums[left] +nums[right] - target = 0，则直接返回结果即可 -
nums[i] + nums[left] +nums[right] < target，当总值小于target值，则需要Left的指针右移
-
当
Left == RIght时，遍历终止，进入下一个i的遍历查找
image-20210424103626024
CODE
class Solution {
public int threeSumClosest(int[] nums, int target) {
//默认值
int res = nums[0] + nums[1] + nums[2];
//排序
Arrays.sort(nums);
int len = nums.length;
for(int i =0; i < len ; i++){
int left = i+1;
int right = len-1;
//左右指针位置对比，防止越界
while(left < right){
//三数之和
int sum = nums[i]+nums[left]+nums[right];
//三数之和 与 target之间的绝对差距
int absRes = Math.abs(sum-target);
//如果当前结果值与target的绝对值，比最小的绝对值小，则替换最下绝对值res的值
if(Math.abs(sum-target)<=Math.abs(res-target)){
res = sum;
}
//当前总数 大于 target，右指针左移
if(sum > target){
right--;
//当前总数 小于 target，左指针右移
}else if(sum < target){
left++ ;
}else{
//相等直接返回
return res;
}
}
}
return res;
}
}
复杂度
- 时间复杂度：
O(2^N)
空间复杂度：O(1)
结果
- 执行用时：
7ms, 在所有Java提交中击败了38.64%的用户 - 内存消耗：
37.9MB, 在所有Java提交中击败了93.44%的用户
LeetCode名句
超时? 淦!
