[LeetCode] 16. 3Sum Closest

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:
Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

Constraints:
3 <= nums.length <= 500
-1000 <= nums[i] <= 1000
-104 <= target <= 104

最接近的三数之和。

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

返回这三个数的和。

假定每组输入只存在恰好一个解。

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

思路

题意是给一个数组和一个 target 数字，返回一个三数之和使得 nums[A] + nums[B] + nums[C] = target 或尽可能接近 target。

思路跟15题类似，也是需要先排序。排序之后，先固定第一个数字，然后后两个数字之间做 two pointer 逼近。逼近的方式是如果

• res = nums[A] + nums[B] + nums[C] = target，则直接返回这个res；
• 如果res大于target，C–
• 如果res小于target，B++

注意在排序过后， res 的初始化是 res = nums[0] + nums[1] + nums[nums.length - 1]。因为这个值是全局最小的三数之和。

复杂度

时间O(n^2) - worst case
空间O(1)

代码

Java实现

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int res = nums[0] + nums[1] + nums[n - 1];
        for (int i = 0; i < n - 2; i++) {
            int lo = i + 1;
            int hi = n - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (Math.abs(sum - target) < Math.abs(res - target)) {
                    res = sum;
                }
                if (sum > target) {
                    hi--;
                } else {
                    lo++;
                }
            }
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    nums = nums.sort((a, b) => a - b);
    const len = nums.length;
    let res = nums[0] + nums[1] + nums[len - 1];
    let low, high, sum;
    for (let i = 0; i < nums.length - 2; i++) {
        low = i + 1;
        high = nums.length - 1;
        while (low < high) {
            sum = nums[i] + nums[low] + nums[high];
            if (Math.abs(target - sum) < Math.abs(target - res)) {
                res = sum;
            }
            if (sum > target) {
                high--;
            } else {
                low++;
            }
        }
    }
    return res;
};