LeetCode每日一题，最接近的三数之和

题目

最接近的三数之和

https://leetcode-cn.com/problems/3sum-closest/

公众号 《java编程手记》记录JAVA学习日常，分享学习路上点点滴滴，从入门到放弃，欢迎关注

描述

难度：中等

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

示例 1：

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

Solution

双指针解法

解题思路

题目条件

跟昨天写的三数之和差不多，唯一不同的点在于，三数之和是求出a+b+c=0的三个数，这题求得是a+b+c的值最接近target

暴力解法我就不过多讲解了，直接多重FOR循环遍历求值即可，找到小于当前最小值的就替换，但是 最终提交结果八成也是超时

还是使用双指针的方式

• 我们先将nums进行从小到大的排序，对排序后的数组循环遍历，

• 使用双指针分别指向当前nums[i]的右侧和nums数组的最右侧

• 计算 nums[i] + nums[left] +nums[right] 的值

  • nums[i] + nums[left] +nums[right] > target，当前总值大于target值 ，在上一步已经进行了由小到大的排序，则需要Right的指针左移
  • nums[i] + nums[left] +nums[right] - target = 0 ，则直接返回结果即可
  • nums[i] + nums[left] +nums[right] < target，当总值小于target值，则需要Left的指针右移

• 当Left == RIght 时，遍历终止，进入下一个i的遍历查找

image-20210424103626024

CODE

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        //默认值
        int res = nums[0] + nums[1] + nums[2];
        //排序
        Arrays.sort(nums);
        int len = nums.length;
        for(int i =0; i < len ; i++){
            int left = i+1;
            int right = len-1;
            //左右指针位置对比，防止越界
            while(left < right){
                //三数之和
                int sum = nums[i]+nums[left]+nums[right];
                //三数之和 与 target之间的绝对差距
                int absRes = Math.abs(sum-target);
                //如果当前结果值与target的绝对值，比最小的绝对值小，则替换最下绝对值res的值
                if(Math.abs(sum-target)<=Math.abs(res-target)){
                    res = sum;
                }
                //当前总数 大于 target，右指针左移
                if(sum > target){
                    right--;
                //当前总数 小于 target，左指针右移
                }else if(sum < target){
                    left++ ;
                }else{
                    //相等直接返回
                    return res;
                }
            }
        }
        return res;
    }
}

复杂度

• 时间复杂度：O(2^N)
  空间复杂度：O(1)

结果

• 执行用时：7 ms, 在所有 Java 提交中击败了38.64%的用户
• 内存消耗：37.9 MB, 在所有 Java 提交中击败了93.44%的用户

LeetCode名句

超时? 淦!