LeetCode 16. 最接近的三数之和

比眉伴天荒 2022-02-16 13:56 222阅读 0赞

github：[https://github.com/Renhongqiang/LeetCode][https_github.com_Renhongqiang_LeetCode]

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

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
    
    与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

--------------------

**思路:**  
三数之和：[https://blog.csdn.net/qq\_37499840/article/details/89453033][https_blog.csdn.net_qq_37499840_article_details_89453033]

类比三数之和：依然排序，遍历nums，每次遍历为 nums\[i\] 设置 l=i+1、r=nums.length-1，l++、r--，使用rst记录目前最接近target的值，与遍历到的 nums\[i\] + nums\[l\] + nums\[r\] 比较，取二者中最接近 target 的值，然后判断 temp（三数和） 与 target 的大小关系，temp < target  则 l 右移，因为升序排序，否则  r 左移，如果相等则直接返回target。

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

[https_github.com_Renhongqiang_LeetCode]: https://github.com/Renhongqiang/LeetCode
[https_blog.csdn.net_qq_37499840_article_details_89453033]: https://blog.csdn.net/qq_37499840/article/details/89453033