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%!!!(代码非原创,同样的思路,结果没有这么理想,不得不膜拜一分钟啊)