16. 最接近的三数之和

一、题目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和

假定每组输入只存在唯一答案。

• 3 <= nums.length <= 10^3
• -10^3 <= nums[i] <= 10^3
• -10^4 <= target <= 10^4

二、解题思路

原理和求3数之和一样，把它转换成找2数之和，问题就变得稍微容易一些。

• a + b + c = target 可以转成 b + c = target - a，那么就相当于查找2数之和

2数之和就快很多了。

三、复杂度分析

• 时间 O(n^2)
• 空间 O(1)

四、参考代码

/**
 * 最近的3数之和
 * @param nums 数组
 * @param target 目标值
 * @return 3数之和
 */
private int threeSumClosest(int[] nums, int target) {
    int closestSum = 0;
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        int sum = twoSumClosest(nums, target - nums[i], i + 1, nums.length - 1);
        sum += nums[i];
        if (sum == target) {
            return sum;
        }
        // 取最接近的值
        if (i == 0 || Math.abs(sum - target) < Math.abs(closestSum - target)) {
            closestSum = sum;
        }
    }
    return closestSum;
}

/**
 * 最近的2数之和
 * @param nums 排序数组
 * @param target 目标值
 * @param start 起始索引
 * @param end 终止索引
 * @return 2数之和
 */
private int twoSumClosest(int[] nums, int target, int start, int end) {
    int lp = start, rp = end;
    int sum = nums[lp] + nums[rp];
    while (lp < rp) {
        int temp = nums[lp] + nums[rp];
        if (temp == target) {
            return target;
        }
        if (Math.abs(temp - target) < Math.abs(sum - target)) {
            sum = temp;
        }
        if (temp < target) {
            lp++;
        } else {
            rp--;
        }
    }
    return sum;
}