文章目录
前言
解题思路
代码
前言
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
跟三数之和思路差不多,使用双指针
重点是如何判断差值的距离
使用Math.abs(target-三个数的和)越小,距离就越近
先给数组排序
固定好i,
在i+1到n-1的范围找出sum
如果sum>target,那么r–,
否则l++
代码
class Solution {
public int threeSumClosest(int[] nums, int target) {
int n=nums.length;
Arrays.sort(nums);
int ans=Integer.MAX_VALUE;
for(int i=0;i<n-2;i++){
int l=i+1;
int r=n-1;
while(l<r){
int sum=nums[i]+nums[l]+nums[r];
if(sum==target){
return sum;
}
if(Math.abs(target-sum)<=Math.abs(target-ans)){
ans=nums[i]+nums[l]+nums[r];
}
if(sum>target){
r--;
}else{
l++;
}
// 排除相同的数
// if (sum > target) {
// int r0 = r - 1;
// while (l < r0 && nums[r0] == nums[r]) {
// --r0;
// }
// r = r0;
// } else {
// int l0 = l + 1;
// while (l0 < r && nums[l0] == nums[l]) {
// ++l0;
// }
// l = l0;
// }
}
}
return ans;
}
}
