16. Sum of the nearest three numbers

---

前言

给你一个长度为 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
著作权归领扣网络所有.商业转载请联系官方授权,非商业转载请注明出处.

解题思路

Similar to the idea of ​​the sum of three,使用双指针
The point is how to judge the distance of the difference
使用Math.abs(target-三个数的和)越小,距离就越近
先给数组排序
固定好i,
在i+1到n-1range to find outsum
如果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++;
                }
                // Exclude the same numbers
                // 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;
    }
}