16. 最接近的三数之和

青旅半醒 2022-09-08 13:51 136阅读 0赞

[https://leetcode-cn.com/problems/3sum-closest/][https_leetcode-cn.com_problems_3sum-closest]

难度中等859收藏分享切换为英文接收动态反馈

给定一个包括 *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`

通过次数248,659提交次数540,854

class Solution {
        public int threeSumClosest(int[] nums, int target) {
            int ans = 10000000 ;
            Arrays.sort(nums);
            int n=10000000;
    
            for(int a = 0;a<nums.length-2;a++)
            {
                //避免重复值
                if(a>0 && nums[a]==nums[a-1]) continue;
    
                for(int b = a+1,c=nums.length-1;b<c;b++)
                {
                    c=nums.length-1;
                    while(b<c && target < (nums[a]+nums[b]+nums[c]))
                    {                    
                        if(Math.abs(target-ans) > Math.abs(target-(nums[a]+nums[b]+nums[c])))
                        {                        
                            ans = nums[a]+nums[b]+nums[c];                        
                        } 
                        c--;
                    } 
                    if(b<c && c+1<nums.length)
                    {
                        if(Math.abs(target-(nums[a]+nums[b]+nums[c])) < Math.abs(target-(nums[a]+nums[b]+nums[c+1])))
                        {
                            n = (nums[a]+nums[b]+nums[c]);
                        }
                        else n = (nums[a]+nums[b]+nums[c+1]);
                    }
                    else if(a!=b && b!=c && Math.abs(target-ans) > Math.abs(target-(nums[a]+nums[b]+nums[c])))
                    {
                        ans = nums[a]+nums[b]+nums[c];
                        System.out.println(nums[a]+" "+nums[b]+"  "+nums[c]);
                    }
                    if(Math.abs(n-target)<Math.abs(ans-target))  ans = n;  
                }            
            }
            return ans;
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_18_color_FFFFFF_t_70_g_se_x_16][]

[https_leetcode-cn.com_problems_3sum-closest]: https://leetcode-cn.com/problems/3sum-closest/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/573113f29c7146f49777fd98336169bd.png