当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.016.3Sum Closest 最接近的三数之和

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 的值
lefti + 1 开始往后移动,rightnums.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


上一篇 LeetCode.139.Word Break 单词拆分

下一篇 LeetCode.067.Add Binary 二进制求和

阅读
评论
548
阅读预计2分钟
创建日期 2020-06-24
修改日期 2020-06-24
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论