16. 最接近的三数之和 Medium

给你一个长度为 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
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

解题思路

输入：一个整数数组 nums，一个目标值 target

输出：找出三个数之和最接近 target 并返回

本题是典型的 排序 + 相向双指针 问题。

这道题和三数之和类似，我们需要先排序，先固定一个数然后通过左右指针在这个数的右侧不断找三个数之和最接近 target 的组合

每次都计算当前组合的总和 currentSum，并更新最接近 target 的总和 closestSum

当前组合如果比 target 小，说明需要移动左指针让整个组合结果变大

如果比 target 大，则移动右指针让整个组合结果变小

如果发现相加等于 target 则直接返回 target

最终遍历完后返回最后记录的最接近 target 的和 closestSum

代码实现

python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # 先对数组排序，为使用双指针做准备
        nums.sort()
        n = len(nums)
        
        # 初始化一个最接近目标值的和，设置为无限大
        closest_sum = float('inf')

        # 遍历数组，每次固定一个数 nums[i]
        for i in range(n - 2):
            left = i + 1              # 左指针从 i 的右边开始
            right = n - 1             # 右指针从数组末尾开始

            # 使用双指针夹逼查找最接近 target 的三个数之和
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]

                # 如果当前的三数之和比之前记录的更接近 target，就更新 closest_sum
                if abs(target - current_sum) < abs(target - closest_sum):
                    closest_sum = current_sum

                # 根据当前和与目标值的比较来移动指针
                if current_sum < target:
                    left += 1  # 当前和太小了，左指针右移以增大总和
                elif current_sum > target:
                    right -= 1 # 当前和太大了，右指针左移以减小总和
                else:
                    # 如果刚好等于目标值，说明已经是最优解了，直接返回
                    return target

        # 返回最终最接近目标值的三个数之和
        return closest_sum

javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    nums.sort((a, b) => a - b);
    let closestSum = Infinity;

    for (let i = 0; i < nums.length - 2; i++) {
        let left = i + 1;
        let right = nums.length - 1;

        while (left < right) {
            const currentSum = nums[i] + nums[left] + nums[right];

            if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
                closestSum = currentSum
            }

            if (currentSum < target) {
                left++;
            } else if (currentSum > target) {
                right--;
            } else {
                return target;
            }
        }
    }

    return closestSum;
};

复杂度分析

时间复杂度：O(n^2)

空间复杂度：O(1)

链接

16 国际版

16 中文版