开发者社区> 游客z3jcatjk57fiu> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

每日算法系列【LeetCode 16】最接近的三数之和

简介: 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
+关注继续查看

题目描述


给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例1

输入:
nums = [-1,2,1,-4], target = 1.
输出:
2
解释:
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

题解


image.png

代码


c++

class Solution {
    public: 
    int threeSumClosest(vector<int>& nums, int target) { 
        int n = nums.size(), res = 10000000;  
        sort(nums.begin(), nums.end()
            );    
        for (int i = 0; i < n - 2; ++i) {
            int l = i + 1, r = n - 1;  
            while (l < r) {  
                int sum = nums[i] + nums[l] + nums[r]; 
                if (sum == target) return sum;  
                if (abs(sum-target) < abs(res-target)) res = sum;
                if (sum > target) r--;   
                else l++;     
            }     
        }    
        return res;  
    }
};

python

class Solution: 
    def threeSumClosest(self, nums: List[int], target: int) -> int:        n, res = len(nums), 10000000  
        nums.sort() 
        for i in range(n-2):  
            l, r = i+1, n-1   
            while l < r:  
                s = nums[i] + nums[l] + nums[r]    
                if s == target:  
                    return s   
                if abs(s-target) < abs(res-target):   
                    res = s      
                    if s > target: 
                        r -= 1     
                        else:      
                            l += 1  
                            return res

image.png

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习喜欢与人分享技术与知识,期待与你的进一步交流~


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
每日算法系列【LeetCode 684】冗余连接
在本问题中, 树指的是一个连通且无环的无向图。 输入一个图,该图由一个有着 个节点(节点值不重复 )的树及一条附加的边构成。附加的边的两个顶点包含在 到 中间,这条附加的边不属于树中已存在的边。 结果图是一个以边组成的二维数组。每一个边的元素是一对 ,满足 ,表示连接顶点 和 的无向图的边。 返回一条可以删去的边,使得结果图是一个有着 个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边 应满足相同的格式.
13 0
每日算法系列【LeetCode 386】字典序排数
给定一个整数 n, 返回从 1 到 n 的字典顺序。 例如,给定 n = 13,返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。 请尽可能的优化算法的时间复杂度和空间复杂度。输入的数据 n 小于等于 5,000,000。
26 0
LeetCode 16-20 题 详解 Java版 ( 万字 图文详解 LeetCode 算法题16-20 =====>>> <建议收藏>)
LeetCode 16-20 题 详解 Java版 ( 万字 图文详解 LeetCode 算法题16-20 =====>>> <建议收藏>)
10 0
每日算法系列【LeetCode 881】救生艇
第 i 个人的体重为 people[i],每艘船可以承载的最大重量为 limit。 每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit。 返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
31 0
leetcode算法1.两数之和
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
18 0
​LeetCode刷题实战16: 最接近的三数之和
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
14 0
Leetcode打卡 | No.016 最接近的三数之和
欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!
28 0
LeetCode解题之十三:搜索插入位置
LeetCode解题之十三:搜索插入位置
27 0
LeetCode刷题2006-简单-差的绝对值为 K 的数对数目
LeetCode刷题2006-简单-差的绝对值为 K 的数对数目
37 0
217
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载