16.最接近的三數(shù)之和
https://leetcode-cn.com/problems/3sum-closest/
難度：中等
題目：
給定一個包括n 個整數(shù)的數(shù)組nums和 一個目標值target。找出nums中的三個整數(shù)贤笆，
使得它們的和與target最接近蝇棉。返回這三個數(shù)的和。假定每組輸入只存在唯一答案芥永。
提示：
- 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目標值的三數(shù)之和埋涧。
首先拿到這種題板辽，我們要先看下提示中的取值范圍，3 <= nums.length <= 10^3條件標志著飞袋。
不會出現(xiàn)不足三個數(shù)字的異常場景戳气，但10^3 如果三層for循環(huán)10^9必然會超時，暴力解法不通巧鸭。
那么瓶您，下來就需要考慮優(yōu)化方案：
- 二分查找 or hash表？
- 二分查找和hash表只針對單個數(shù)字纲仍，那勢必我們需要先雙層循環(huán)再二分呀袱，10^6一樣會超時。
- 縮減條件
- 既然三個數(shù)字我們有些無從下手郑叠，那么先使用一層for循環(huán)夜赵，減少一個數(shù)字的篩選再來考慮是否就簡單了一些。
- 減少一個數(shù)字后乡革，我們的題目變成了查找數(shù)組中某兩個最接近target - num1寇僧，是不就變成了一道基礎(chǔ)題。
- 實現(xiàn)方案
- 我們先將nums排序
- 設(shè)置返回值ret沸版，初始為float('inf')無窮大
- 開始
for i in range(len(nums))循環(huán) - 設(shè)置left = i + 1,right = length - 1
- tmp = nums[left] + nums[rigth]
- 比較 ret和tmp+nums[i]嘁傀，哪個更接近target，并賦值給ret
- 如果tmp = target - nums[i],表示找到了三個數(shù)等于target直接返回target
- 如果tmp > target - nums[i],我們將right -= 1
- 如果tmp < target - nums[i],我們將left -= 1
最終视粮，即可獲取結(jié)果细办。
解題：
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
歡迎關(guān)注我的公眾號: 清風Python，帶你每日學習Python算法刷題的同時蕾殴，了解更多python小知識笑撞。
我的個人博客：https://qingfengpython.cn
