16.最接近的三数之和(python)
【题目】
【思路】
先将nums排序,计算temp = nums[i]+nums[left]+nums[right]。
判断若temp>target,那就希望temp小一点,right左移(变小)。
ps:今天时间比较匆忙要赶飞机回家了,借鉴了小伙伴的代码,觉得还可以从二分法进行效率提高。也就是分别用left与middle,还有left和right来计算temp。选择更接近target的组合,再分成新的left、middle和right,可以提升效率。
【python】
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
#先将数排序
nums.sort()
#初始化res,用前三个数之和
res = sum(nums[:3])
#i遍历nums,每次循环left和right分别向中间移动
for i in range(len(nums)):
left = i+1
right = len(nums)-1
while left<right:
temp = nums[i]+nums[left]+nums[right]
#abs相减判断,res替换更接近target的值
if abs(res-target) > abs(temp-target):
res = temp
#判断是left右移还是right左移
if temp>target:
right = right-1
else:
left = left+1
return res
【结果】