力扣每日一题：16.最接近的三数之和 双指针解法
2021-05-04 本文已影响0人
清风Python
16.最接近的三数之和
https://leetcode-cn.com/problems/3sum-closest/
难度：中等
题目：
给定一个包括n 个整数的数组nums和 一个目标值target。找出nums中的三个整数，
使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。
提示：
- 3 <= nums.length <= 10^3
- -10^3 <= nums[i] <= 10^3
- -10^4 <= target <= 10^4
示例：
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
分析
这道题的题目比较短，获取最接近target目标值的三数之和。
首先拿到这种题，我们要先看下提示中的取值范围，3 <= nums.length <= 10^3条件标志着。
不会出现不足三个数字的异常场景，但10^3 如果三层for循环10^9必然会超时，暴力解法不通。
那么，下来就需要考虑优化方案：
- 二分查找 or hash表？
- 二分查找和hash表只针对单个数字，那势必我们需要先双层循环再二分，10^6一样会超时。
- 缩减条件
- 既然三个数字我们有些无从下手，那么先使用一层for循环，减少一个数字的筛选再来考虑是否就简单了一些。
- 减少一个数字后，我们的题目变成了查找数组中某两个最接近target - num1，是不就变成了一道基础题。
- 实现方案
- 我们先将nums排序
- 设置返回值ret，初始为float('inf')无穷大
- 开始
for i in range(len(nums))循环 - 设置left = i + 1,right = length - 1
- tmp = nums[left] + nums[rigth]
- 比较 ret和tmp+nums[i]，哪个更接近target，并赋值给ret
- 如果tmp = target - nums[i],表示找到了三个数等于target直接返回target
- 如果tmp > target - nums[i],我们将right -= 1
- 如果tmp < target - nums[i],我们将left -= 1
最终，即可获取结果。
解题：
class Solution:
def threeSumClosest(self, nums, target):
ret = float('inf')
nums.sort()
length = len(nums)
for i in range(length - 2):
left = i + 1
right = length - 1
while left < right:
tmp = nums[i] + nums[left] + nums[right]
ret = tmp if abs(tmp - target) < abs(ret - target) else ret
if tmp == target:
return target
if tmp > target:
right -= 1
else:
left += 1
return ret
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
