[leetcode] 16. 最接近的三数之和

题目描述

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

输入：nums = [0,0,0], target = 1
输出：0

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -10⁴ <= target <= 10⁴

解题方法

排序 + 双指针

本题与leetcode第15题相似，这次我介绍一种排序 + 双指针的解法，以下部分请结合代码进行理解。

我们先将$nums$数组按照从小到大排序。然后最外层从数组开头开始遍历，指针$i$初始位置为0，内层每整体遍历完一次，$i++$；内层的遍历设置双指针，$l$初始在$i+1$的位置，$r$初始在数组末尾。当$nums[i]+nums[l]+nums[r]<=target$时，$l++$；当$nums[i]+nums[l]+nums[r]>target$时，$r??$。这样保证了三数之和始终在$target$上下波动。当$l==r$后，遍历结束。在这个过程中，我们不断更新最接近$target$的三数之和。

此外，我们还有一个小优化。每次遍历时，当指针遍历到的数字与上一次遍历的数字相等时，直接跳过这次遍历，指针移动到下一个位置。为什么要这样做呢？因为此时三数之和与上一次三数之和相等，所以指针也保持上一次的移动方向再移动一次。

java代码

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    // 最接近target的结果
    int result = nums[0] + nums[1] + nums[nums.length - 1];
    // 离target最接近的数字间距
    int minInterval = Math.abs(result - target);
    for (int i = 0; i < nums.length - 2; i++) {
        if (i != 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int l = i + 1;
        int r = nums.length - 1;
        while (l < r) {
            // 判断与上一个数字是否相等
            if (l != i + 1 && nums[l] == nums[l - 1]) {
                l++;
                continue;
            }
            if (r != nums.length - 1 && nums[r] == nums[r + 1]) {
                r--;
                continue;
            }
            int val = nums[i] + nums[l] + nums[r];
            // 三数之和小于target，l++；三数之和大于target，r--
            if (val <= target) {
                l++;
            } else {
                r--;
            }
            // 不断更新最接近的三数之和以及最小间距
            int curInterval = Math.abs(val - target);
            if (curInterval < minInterval) {
                result = val;
                minInterval = curInterval;
            }
        }
    }
    return result;
}

时间复杂度：$O(N^2)$。$N$为数组长度，排序时间复杂度$O(NlogN)$，双指针遍历时间复杂度$O(N^2)$，两者相加为$O(N^2)$。
空间复杂度：$O(1)$

相似题目

[leetcode] 1. 两数相加
[leetcode] 15. 三数之和

---

• 个人公众号
  
• 个人小游戏