Leetcode打卡 | No.016 最接近的三数之和

简介: 欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!


No.16  最接近的三数之和

题目:

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

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.


与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

题目分析:

这一题,基本上数之和都有一大家子了。两数之和;三数之和;最接近的三数之和……相信上一题(三数之和)大家多少还有些印象,没有的自行去复习噢。

上一题我们是首先进行排序,将数组进行从小到大的排序,之后固定一个数,在这个数之和,选择从两端进行向中间的逼近。这里思路如下:

  1. 列表排序,sort()方法
  2. 一层循环,固定一个数(索引记为 i),在这个数之后,记 l 指向第一个数,r 指向最后一个数
  3. 如果nums[i]+nums[l]+nums[l+1]大于目标值,那么在nums[i]固定情况下,其他情况只会更大于目标值,此时直接append进目标列表
  4. 如果nums[i]+nums[r]+nums[r-1]小于目标值,那么在nums[i]固定情况下,其他情况只会更小于目标值,此时直接append进目标列表
  5. 其他情况下,当l在r的左边,即第二个数小于第三个数时,继续向下执行。先将这时append进目标列表,并判断nums[i]+nums[l]+nums[r]三数之和和目标值关系,大于目标值,则r减一(最大数减小);小于目标值则l加一(最小数增加);恰好等于直接返回即可(仅有一个解)
  6. 执行完所有循环,则所有可能的答案都在目标列表中,对列表按照与目标值之差的绝对值排序,返回第一个(即差最小,也即最接近的三数之和)

代码如下:

39.jpg


运行结果如下,beat100%!!!(代码非原创,同样的思路,结果没有这么理想,不得不膜拜一分钟啊)

40.jpg

相关文章
|
3月前
|
算法
LeetCode第16题最接近的三数之和
该文章介绍了 LeetCode 第 16 题最接近的三数之和的解法,与第 15 题类似,通过双指针法减少循环次数,根据差值的绝对值来更新最接近的和,并总结了双指针可减少循环次数的要点。
|
3月前
|
Python
【Leetcode刷题Python】16. 最接近的三数之和
解决LeetCode "最接近的三数之和" 问题的Python实现,通过排序和双指针法,记录并更新与目标值最接近的三数之和。
37 1
|
5月前
|
存储 算法 数据挖掘
LeetCode第十六题: 掌握双指针技巧 最接近的三数之和 【python】
LeetCode第十六题: 掌握双指针技巧 最接近的三数之和 【python】
|
6月前
leetcode-16:最接近的三数之和
leetcode-16:最接近的三数之和
50 0
【LeetCode-每日一题】-16. 最接近的三数之和
【LeetCode-每日一题】-16. 最接近的三数之和
|
11月前
|
Java
1657. 确定两个字符串是否接近 --力扣 --JAVA
如果可以使用以下操作从一个字符串得到另一个字符串,则认为两个字符串 接近 : 操作 1:交换任意两个 现有 字符。 例如,abcde -> aecdb 操作 2:将一个 现有 字符的每次出现转换为另一个 现有 字符,并对另一个字符执行相同的操作。 例如,aacabb -> bbcbaa(所有 a 转化为 b ,而所有的 b 转换为 a ) 你可以根据需要对任意一个字符串多次使用这两种操作。 给你两个字符串,word1 和 word2 。如果 word1 和 word2 接近 ,就返回 true ;否则,返回 false 。
43 0
LeetCode: 16. 最接近的三数之和 | 双指针专题
【LeetCode: 16. 最接近的三数之和 | 双指针专题 】
56 1
|
存储 算法 Python
【力扣算法01】之最接近的三数之和
【力扣算法01】之最接近的三数之和
80 0
|
测试技术 C++
力扣16-最接近的三数之和&力扣18-四数之和
力扣16-最接近的三数之和&力扣18-四数之和
83 0
|
算法 安全 Swift
LeetCode - #16 最接近的三数之和
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。