Leetcode打卡 | No.016 最接近的三数之和
写在前边:
欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!
No.16 最接近的三数之和
题目:
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
题目分析:
这一题,基本上数之和都有一大家子了。两数之和;三数之和;最接近的三数之和……相信上一题(三数之和)大家多少还有些印象,没有的自行去复习噢。
上一题我们是首先进行排序,将数组进行从小到大的排序,之后固定一个数,在这个数之和,选择从两端进行向中间的逼近。这里思路如下:
列表排序,sort()方法
一层循环,固定一个数(索引记为 i),在这个数之后,记 l 指向第一个数,r 指向最后一个数
如果nums[i]+nums[l]+nums[l+1]大于目标值,那么在nums[i]固定情况下,其他情况只会更大于目标值,此时直接append进目标列表
如果nums[i]+nums[r]+nums[r-1]小于目标值,那么在nums[i]固定情况下,其他情况只会更小于目标值,此时直接append进目标列表
其他情况下,当l在r的左边,即第二个数小于第三个数时,继续向下执行。先将这时append进目标列表,并判断nums[i]+nums[l]+nums[r]三数之和和目标值关系,大于目标值,则r减一(最大数减小);小于目标值则l加一(最小数增加);恰好等于直接返回即可(仅有一个解)
执行完所有循环,则所有可能的答案都在目标列表中,对列表按照与目标值之差的绝对值排序,返回第一个(即差最小,也即最接近的三数之和)
代码如下:
运行结果如下,beat100%!!!(代码非原创,同样的思路,结果没有这么理想,不得不膜拜一分钟啊)
原文发布时间为:2018-07-13
本文作者:小詹同学
本文来自云栖社区合作伙伴“小詹学Python”,了解相关信息可以关注“小詹学Python”。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Function执行原理 & 闭包
Execution Context 执行期上下文 在java或c语言中,都有块级作用域这个概念,而js中则没有。 在js中,作用域只有一种,即函数级作用域。 而执行期上下文,可以理解为函数的作用域或执行环境。 在代码层面,执行期上下文是嵌套存在的 在js引擎内,执行期上下文是以栈的形式进行存放 栈的最底部存放的global上下文,每次执行一个函数,则会创建一个上下文放入栈中,执行结束后再pop移除。 (function foo(i) { if (i === 3) { return; } else { foo(++i); } }(0)); 当前的执行环境则永远使用存放在栈顶的上下文对象。 参考博文: 深入理解Javascript之执行上下文(Execution Context) -- JavaScript -- IT技术博客大学习 -- 共学习 共进步! 深入理解JavaScript系列(10):JavaScript核心(晋级高手必读篇) - 汤姆大叔 - 博客园 Function 执行原理 js中有在function上面有很多的用法和概念,就比如作用域链,闭包这些。 其实问题归结到了根...
- 下一篇
经典编程书籍大全
100+ 经典技术书籍,涵盖:计算机系统与网络、系统架构、算法与数据结构、前端开发、后端开发、移动开发、数据库、测试、项目与团队、程序员职业修炼、求职面试 和 编程相关的经典书籍。 计算机系统与网络 《图灵的秘密:他的生平、思想及论文解读》 《计算机系统概论》 《深入理解Linux内核》 《深入Linux内核架构》 《TCP/IP详解 卷1:协议》 《Linux系统编程(第2版)》 《Linux内核设计与实现(第3版)》 《深入理解计算机系统(原书第2版)》 《计算机程序的构造和解释(原书第2版)》 《编码:隐匿在计算机软硬件背后的语言》 《性能之颠:洞悉系统、企业与云计算》 《UNIX网络编程 卷1:套接字联网API(第3版)》 《UNIX网络编程 卷2:进程间通信》 《Windows核心编程(第5版)》 《WireShark网络分析就这么简单》 《WireShark网络分析的艺术》 编程通用 《编程原本》 《代码大全》 《UNIX编程艺术》 《代码整洁之道》 《编程珠玑(第2版)》 《编程珠玑(续)》 《软件调试的艺术》 《修改代码的艺术》 《编程语言实现模式》 《编写可读代码的艺...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS6,CentOS7官方镜像安装Oracle11G
- CentOS8编译安装MySQL8.0.19
- Windows10,CentOS7,CentOS8安装Nodejs环境
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- SpringBoot2整合Thymeleaf,官方推荐html解决方案