概述
16. 最接近的三数之和
给定一个包括 n 个整数的数组 nums
和 一个目标值 target
。找出 nums
中的三个整数,使得它们的和与 target
最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
这道题和15 - 三数之和 - python区别并不大,所以可以重用大部分的代码。分析题意,题目要求在数组中找到三个数使其之和最接近与target
,并且答案唯一,那么:
- 当数组元素个数小于3时,直接返回None,表示答案不存在
- 当数组元素个数等于3时,直接返回数组之和
- 当数组元素个数大于3时,需要设置
minDiff
记录当前三数之和和target
的差距,同样设置left
和right
两个指针,然后重复以下判断过程,直到left >= right
:- 如果
nums[cur] + nums[left] + nums[right] == target
,直接返回三数之和,由于答案唯一,所以这里不需要再移动left
和right
判断其他的情况 - 如果
nums[cur] + nums[left] + nums[right] != target
,则计算与target
的差距,如果它的绝对值小于minDIff
,则需要更新minDiff
,然后同样根据情况更新left
或right
- 如果当前三数之和小于
target
,则left
右移, - 如果当前三数之和大于
target
,则right
左移 - 同样为了避免不必要的判断,这里需要判断当前
left
和right
所指元素和它上一个元素是否相同
- 如果当前三数之和小于
- 如果
AC code
import sys
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
if len(nums) < 3: return None
if len(nums) == 3: return sum(nums)
minDiff = sys.maxsize
nums.sort()
for cur in range(len(nums)-2):
if cur > 1 and nums[cur] == nums[cur - 1]:
continue
left = cur + 1
right = len(nums) - 1
while left < right :
threeSum = nums[cur] + nums[left] + nums[right]
diff = threeSum - target
if diff == 0:
return threeSum
elif abs(diff) < minDiff:
minDiff = abs(diff)
closestSum = threeSum
if diff < 0:
left += 1
while left < right and nums[left]==nums[left - 1]:
left +=1
else:
right -= 1
while left < right and nums[right]==nums[right + 1]:
right -= 1
return closestSum
最后
以上就是现代银耳汤为你收集整理的16 -最接近的三数之和 - python的全部内容,希望文章能够帮你解决16 -最接近的三数之和 - python所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复