最接近的三个数的和
程序员文章站
2024-03-16 20:28:34
...
""" 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 例如,给定数组 nums = [-1,2,1,-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2). 题解: 排序+双指针 算法流程: 特判,对于数组长度 l,如果数组为Null或者数组长度小于3,返回 None。 对数组进行排序,并定义min_num,保存最接近和。 遍历排序后数组: 对于重复元素,跳过,避免重复计算(也可以不跳过) 令左指针Left=i+1,右指针R=n-1,当L<R时,执行循环: *令temp=nums[i]+nums[Left]+nums[Right],如果temp=target,返回target *若abs(temp-target)<abs(min_num-target)说明temp更接近目标,更新min_num *若temp-target大于0,说明nums[Right]太大,Right左移 *若temp-target小于0,说明nums[Left]太小,Left右移 """
class Solution:
def threeSumClosest(self, nums,target) -> int:
l = len(nums)
# 特判,对于数组长度 l,如果数组为Null或者数组长度小于3,返回 None。
if not nums or l < 3: return None
nums = sorted(nums)
min_num = nums[0] + nums[1] + nums[2]
for i in range(l - 1):
# 对于重复元素,跳过,避免重复计算(也可以不跳过)
if (i>0 and nums[i]==nums[i-1]):
continue
left, right = i + 1, l - 1
while left < right:
temp = nums[i] + nums[left] + nums[right]
# temp=nums[i]+nums[Left]+nums[Right],如果temp=target,返回target
if temp == target: return target
# 若abs(temp-target)<abs(min_num-target)说明temp更接近目标,更新min_num
if abs(temp - target) < abs(min_num - target):
min_num = temp
# 若temp-target小于0,说明nums[Left]太小,Left右移
if temp - target < 0:
left += 1
# 若temp-target大于0,说明nums[Right]太大,Right左移
else:
right -= 1
return min_num
测试:
if __name__ == "__main__":
s = Solution()
nums = [-1,2,1,-4]
target = 1.
r = s.threeSumClosest(nums,target)
print(r)
下一篇: 三个数的排序常用方法