LeetCode.016.3Sum Closest 最接近的三数之和

题目描述

16 3Sum Closest
https://leetcode-cn.com/problems/3sum-closest/

给定一个包括 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.001.Two Sum 两数之和
LeetCode.653.Two Sum IV - Input is a BST 两数之和4-输入是BST
LeetCode.532.K-diff Pairs in an Array 数组中的k-diff数对

LeetCode.016.3Sum Closest 最接近的三数之和
LeetCode.015.3Sum 三数之和
18 四数之和
https://leetcode-cn.com/problems/4sum/

---

解题过程

暴力解法是 O(n^3) 三重循环枚举三个值。

排序+双指针

这道题的优化解法和 LeetCode.015.3Sum 三数之和 几乎相同。

我们先对数组升序排序，则外层循环固定 first 值后，可以利用双指针在 O(n) 复杂度内找最接近 target - first 的值
left 从 i + 1 开始往后移动，right 从 nums.length - 1 开始往前移动，每次判断 twosum = nums[left] + nums[right] 和 target - first 的大小，小于则左边界 left 右移以增大 twosum 的值，大于则 right 左移以减小 twosum 的值。

时间复杂度 O(n^2)，其中排序复杂度为 O(nlogn)
空间复杂度 O(nlogn)，排序需要这些空间复杂度

private static class SolutionV202006 {
    public int threeSumClosest(int[] nums, int target) {
        // 升序排序
        Arrays.sort(nums);
        // 最接近的值
        int closest = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < nums.length; i++) {
            // 固定 nums[i] 后的目标值
            int thisTarget = target - nums[i];
            // 固定 nums[i] 后双指针遍历数组
            for (int left = i + 1, right = nums.length - 1; left < right;) {
                int twoSum = nums[left] + nums[right];
                if (twoSum == thisTarget) {
                    return target;
                }
                if (twoSum < thisTarget) {
                    // 小于目标值，左边界右移增加两数之和
                    left++;
                } else {
                    // 大于目标值，右边界左移减少两数之和
                    right--;
                }
                // 更新 closest
                closest = Math.abs(thisTarget - twoSum) < Math.abs(target - closest) ? nums[i] + twoSum : closest;
            }
        }
        return closest;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_016_3SumClosest.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_016_3SumClosest.java

---