最接近的三数之和

此博客链接：https://www.cnblogs.com/ping2yingshi/p/14149395.html

最接近的三数之和

题目链接：https://leetcode-cn.com/problems/3sum-closest/solution/zui-jie-jin-de-san-shu-zhi-he-by-leetcode-solution/

题目

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：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

题解

思路：像三数之和一样，先把数组进行排序，然后使用双指针计算三数之和，最后求差值和最小的值是多少。

代码

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int small=nums[0]+nums[1]+nums[2];    
        for(int i=0;i<nums.length;i++){
            int l=i+1;
            int r=nums.length-1;
            if(i==0||nums[i-1]!=nums[i]){
                while(l<r){
                    if(nums[i]+nums[l]+nums[r]==target)
                        return target;
                    if(Math.abs(nums[i]+nums[l]+nums[r]-target)<Math.abs(small-target)){
                         small=nums[i]+nums[l]+nums[r];
                    while(l<r&&nums[l]==nums[l+1])
                         l++;
                    while(l<r&&nums[r]==nums[r-1])
                    {
                        r--;
                    }
                    }
                    if(small<target)
                      l++;
                    else
                       r--;
                } 
            }
        }
       return small; 
    }
}

结果

目前没有看出来什么错误

修改代码

比较当前三数之和和目标数的大小时，确实应该用当前的三数之和合目标数比较，而不应该用最小值和目标数比较。

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int small=nums[0]+nums[1]+nums[2];    
        for(int i=0;i<nums.length;i++){
            int l=i+1;
            int r=nums.length-1;
            if(i==0||nums[i-1]!=nums[i]){
                while(l<r){
                    if(nums[i]+nums[l]+nums[r]==target)
                        return target;
                    if(Math.abs(nums[i]+nums[l]+nums[r]-target)<Math.abs(small-target)){
                         small=nums[i]+nums[l]+nums[r];
                    while(l<r&&nums[l]==nums[l+1])
                         l++;
                    while(l<r&&nums[r]==nums[r-1])
                    {
                        r--;
                    }
                    }
                    if(nums[i]+nums[l]+nums[r]<target)
                      l++;
                    else
                       r--;
                } 
            }
        }
       return small; 
    }
}

结果

最接近的三数之和

推荐阅读