LeetCode刷题Java版：016.最接近的三数之和

作者：沉默王二
发布时间：2022-08-01T16:14:24.700+0800

---

016.最接近的三数之和

题意

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

难度

中等

示例

输入：nums = [-1,2,1,-4], target = 1

输出：2

解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

分析

本题和 015.三数之和很像，观察min(a + b + c - target)这个表达式，无非就是把上一题的目标值0，换成了指定的target，那么我们照样可以将整个数组排序，继续定一移二，只需要判断的条件稍微修改一下就好。

本来是要尽量向0靠近，这时候只需要尽量向target靠近即可，并没有太大的差别，一样的排序，一样的定一移二，但是相较于 015.三数之和 我们还有一个可以优化的点：

如果找到a + b + c = target的话，可以直接返回了，并不需要再继续找下去，因为这本来就是最优解，而对于 015.三数之和 的话，则要求找出所有的可能。

public class Solution {

 public int threeSumClosest(int[] nums, int target) {

  int res = Integer.MAX_VALUE;

  Arrays.sort (nums);

  for(int i = 0;i < nums.length ;i++){

   if(i > 0 && nums[i] == nums[i - 1])

    continue;

   int lef = i + 1,rig = nums.length  - 1;

   while(lef < rig){

    if(Math.abs (nums[i] + nums[lef] + nums[rig] - target) < Math.abs (res - target)){

     res = nums[i] + nums[lef] + nums[rig];

     while(lef < rig && nums[lef] == nums[lef + 1]) lef++;

     while(lef < rig && nums[rig] == nums[rig - 1]) rig--;

    }

    if(res == target)

     return res;

    if(nums[i] + nums[lef] + nums[rig] < target)

     lef++;

    else

     rig--;

   }

  }

  return res;

 }

}

总结

本题和015.三数之和非常相似，算法的本质内核也一模一样，只有细微的差别。刷题其实就是这样，学会举一反三，遇到不同的题型，尽量去找到和它相似的题型，之前有没有刷过，能不能按照之前的解题思路快速把这道题解出来，再去想办法优化。

力扣链接：https://leetcode.cn/problems/3sum-closest/

016.最接近的三数之和

题意

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

难度

中等

示例

输入：nums = [-1,2,1,-4], target = 1

输出：2

解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

分析

本题和 015.三数之和很像，观察min(a + b + c - target)这个表达式，无非就是把上一题的目标值0，换成了指定的target，那么我们照样可以将整个数组排序，继续定一移二，只需要判断的条件稍微修改一下就好。

本来是要尽量向0靠近，这时候只需要尽量向target靠近即可，并没有太大的差别，一样的排序，一样的定一移二，但是相较于 015.三数之和 我们还有一个可以优化的点：

如果找到a + b + c = target的话，可以直接返回了，并不需要再继续找下去，因为这本来就是最优解，而对于 015.三数之和 的话，则要求找出所有的可能。

public class Solution {

 public int threeSumClosest(int[] nums, int target) {

  int res = Integer.MAX_VALUE;

  Arrays.sort (nums);

  for(int i = 0;i < nums.length ;i++){

   if(i > 0 && nums[i] == nums[i - 1])

    continue;

   int lef = i + 1,rig = nums.length  - 1;

   while(lef < rig){

    if(Math.abs (nums[i] + nums[lef] + nums[rig] - target) < Math.abs (res - target)){

     res = nums[i] + nums[lef] + nums[rig];

     while(lef < rig && nums[lef] == nums[lef + 1]) lef++;

     while(lef < rig && nums[rig] == nums[rig - 1]) rig--;

    }

    if(res == target)

     return res;

    if(nums[i] + nums[lef] + nums[rig] < target)

     lef++;

    else

     rig--;

   }

  }

  return res;

 }

}

总结

本题和015.三数之和非常相似，算法的本质内核也一模一样，只有细微的差别。刷题其实就是这样，学会举一反三，遇到不同的题型，尽量去找到和它相似的题型，之前有没有刷过，能不能按照之前的解题思路快速把这道题解出来，再去想办法优化。

力扣链接：https://leetcode.cn/problems/3sum-closest/

016.最接近的三数之和

题意

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

难度

中等

示例

输入：nums = [-1,2,1,-4], target = 1

输出：2

解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

分析

本题和 015.三数之和很像，观察min(a + b + c - target)这个表达式，无非就是把上一题的目标值0，换成了指定的target，那么我们照样可以将整个数组排序，继续定一移二，只需要判断的条件稍微修改一下就好。

本来是要尽量向0靠近，这时候只需要尽量向target靠近即可，并没有太大的差别，一样的排序，一样的定一移二，但是相较于 015.三数之和 我们还有一个可以优化的点：

如果找到a + b + c = target的话，可以直接返回了，并不需要再继续找下去，因为这本来就是最优解，而对于 015.三数之和 的话，则要求找出所有的可能。

public class Solution {

 public int threeSumClosest(int[] nums, int target) {

  int res = Integer.MAX_VALUE;

  Arrays.sort (nums);

  for(int i = 0;i < nums.length ;i++){

   if(i > 0 && nums[i] == nums[i - 1])

    continue;

   int lef = i + 1,rig = nums.length  - 1;

   while(lef < rig){

    if(Math.abs (nums[i] + nums[lef] + nums[rig] - target) < Math.abs (res - target)){

     res = nums[i] + nums[lef] + nums[rig];

     while(lef < rig && nums[lef] == nums[lef + 1]) lef++;

     while(lef < rig && nums[rig] == nums[rig - 1]) rig--;

    }

    if(res == target)

     return res;

    if(nums[i] + nums[lef] + nums[rig] < target)

     lef++;

    else

     rig--;

   }

  }

  return res;

 }

}

总结

本题和015.三数之和非常相似，算法的本质内核也一模一样，只有细微的差别。刷题其实就是这样，学会举一反三，遇到不同的题型，尽量去找到和它相似的题型，之前有没有刷过，能不能按照之前的解题思路快速把这道题解出来，再去想办法优化。

力扣链接：https://leetcode.cn/problems/3sum-closest/

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412