Go 刷 leetcode｜大厂面试必备变形题

今天为大家讲解 LeetCode 第 16 题，顺藤摸瓜，接着昨天的三数之和 leetcode｜面试常客双指针算法题 

今天为大家分享这道变形题：最接近的三数之和。类似的题目一起讲有利于学习巩固，一起奥利给！

题目描述

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/3sum-closest 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

了解昨天三数之和的话，这道题应该也会有思路，同样适用双指针解法。

此题的算法思路如下：

1. 对数组进行排序（排序是必须的，否则无法判断及指针移动）。
2. 初始化返回结果 ans 为 nums[0] + nums[1] + nums[2]（初始化为Int的最大值也行，反正都是用于判断跟新）
3. 遍历排序后数组，并计算当前指向三数的 sum = nums[i] + nums[l] + nums[r] ：
• 若 abs(target-sum) <  abs(target-ans) （abs 是求绝对值），表示当前 sum 距离更近，则更新结果 ans = sum
• 若 sum < target ，左指针 L 右移
• 若 sum > target，右指针 R 左移

代码实现

//go
func threeSumClosest(nums []int, target int) int {
 sort.Ints(nums) // 排序
 length := len(nums)
 ans := nums[0] + nums[1] + nums[2]
 for i := 0; i < length; i++ {
  l, r := i+1, length-1
  for l < r {
   sum := nums[i] + nums[l] + nums[r]
   if AbsInt(target-sum) < AbsInt(target-ans) {
    ans = sum
   }
   if sum < target {
    l++
   } else if sum > target {
    r--
   } else {
    return ans
   }
  }
 }
 return ans
}

func AbsInt(x int) int {
 if x < 0 {
  return -x
 }
 return x
}

//java
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 排序
        Arrays.sort(nums);
        int closestNum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int l = i + 1, r = nums.length - 1;
            while (l < r){
                int threeSum = nums[l] + nums[r] + nums[i];
                if (Math.abs(threeSum - target) < Math.abs(closestNum - target)) {
                    closestNum = threeSum;
                }
                if (threeSum > target) {
                    r--;
                } else if (threeSum < target) {
                    l++;
                } else {
                    // 如果已经等于target的话, 肯定是最接近的
                    return target;
                }

            }

        }

        return closestNum;
    }

}

郑重声明：

所展示代码已通过 LeetCode 运行通过，请放心食用～