【刷题记录】16. 最接近的三数之和

2022 年 7 月 20 日
本文字数：1011 字
阅读完需：约 3 分钟

一、题目描述

给你一个长度为 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

复制代码

提示：

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

二、思路分析

排序 + 双指针

这道题目其实是上道题【刷题记录】15.三数之和的一个变形，上个题目目的是找到 sum == 0 而这道题是找到 sum == target 或者最接近target的，在上道题目的基础上

根据 sum = L + nums[i] + R 的结果，判断 sum 与目标 target 的距离，如果更近则更新结果 res
判断 sum 与 target 的大小关系时，因为数组有序，如果 sum > target 则 R--，如果 sum < target 则 L++，如果 sum == target 则说明距离为 0 直接返回结果

三、代码实现

class Solution {    public int threeSumClosest(int[] nums, int target) {        Arrays.sort(nums);        //初始化一个res        int res = nums[0] + nums[1] + nums[2];        for (int i = 0; i < nums.length; i++) {            //去重            if (i > 0 && nums[i] == nums[i - 1]) continue;            int R = i + 1, L = nums.length - 1;            while (R < L) {                int sum = nums[R] + nums[L] + nums[i];                if (Math.abs(target - sum) < Math.abs(target - res))                    res = sum;                if (sum > target)                    L--;                else if (sum < target)                    R++;                else                    return res;            }        }        return res;    }}

复制代码

复杂度分析

时间复杂度： $O (n^{2})$ ，其中 n 是数组 nums 的长度。我们首先需要 $O (n lo g n)$ 的时间对数组进行排序，随后在枚举的过程中，使用一重循环 O(n) ：遍历数组，双指针 O(n)：枚举 L 和 R，故一共是 $O (n^{2})$

空间复杂度： $O (l o g n)$ 。排序需要使用 $O (l o g n)$ 的空间，在题目的要求下我们是只是对排序的数组进行了存储，此时为 $O (n)$ n 为数组长度

运行结果

总结

这道题其实就是上个题目的一个变形，只要理解了上个题目的思想，这个题目就比较简单了。

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/13a737326c92de926eafbbe8e】。

WangNing

关注

还未添加个人签名 2020.10.13 加入

一个只想提(快)升(乐)自(摸)我(鱼)的混子选手～

发布

暂无评论

创作场景

【刷题记录】16. 最接近的三数之和

一、题目描述

二、思路分析

三、代码实现

复杂度分析

运行结果

总结

WangNing

评论