========堅持30天刷leetcode=====
題目鏈接:https://leetcode-cn.com/problems/3sum-closest/
先上結果:
分析:關鍵在于特殊情況的判斷,減少遍歷。
class Solution:
def threeSumClosest(self, nums, target):
k=len(nums)
if k<3: return None # 特殊情況: 數組小于3
if k==3: return sum(nums) # 特殊情況: 數組等于3
nums.sort()
if nums[0]+nums[1]+nums[2] >= target: # 特殊情況: 最小3個數和 大于等于target
return nums[0]+nums[1]+nums[2]
if nums[k-3]+nums[k-2]+nums[k-1]<=target: # 特殊情況: 最大3個數和 小于等于target
return nums[k-3]+nums[k-2]+nums[k-1]
result=0 # 標記變量
min_gap=float("inf")
for a in range(k-2): # 遍歷數組:從第一個數->倒數第三個數
b=a+1 # 移動變量
c=k-1
if nums[a]+nums[b]+nums[b+1] > target: # 特殊:當前數+最小的2個數 > target
csum=nums[a]+nums[b]+nums[b+1]
gap=abs(target-csum)
if gap
< target
csum=nums[a]+nums[c-1]+nums[c]
gap=abs(target-csum)
if gap
< c and nums[b-1] == nums[b]: b+= 1 # 特殊:數組內存在相同的數
else:
c-=1
while b < c and nums[c] == nums[c+1]: c-= 1 # 特殊:數組內存在相同的數
return result
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
