1.Description:
?
Given an array?
nums
?of?
n
?integers, are there elements?
a
,?
b
,?
c
?in?
nums
?such that?
a
?+?
b
?+?
c
?= 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
2.Ideas:
?
這道題需要從一個列表中選出所有滿足和為0的三元組,且要求去重,最簡單的思路就是暴力的3層循環,這樣肯定會超時。我們可以簡單的進行分析,三個數的和為零,可以先確定一個數,然后再確定另外兩個數,使另外兩個數的和為第一個確定數的相反數,這樣就可以將O(n^3)轉為O(n^2)。我們可以讓第一個確定的數為一個不大于0的數,而且,因為最快的排序算法的時間復雜度是O(nlogn)
3.Code:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
L = []
nums.sort()
length = len(nums)
if(length<3):
return L
for i in range(length-2):
if(nums[i]>0):#三個大于0的數之和不會是0
break
if(i>0 and nums[i]==nums[i-1]):#去掉重復的情況
continue
target = -nums[i]
left = i+1
right = length-1
while left < right:
if(nums[left]+nums[right]==target):
temp = []
temp.append(nums[i])
temp.append(nums[left])
temp.append(nums[right])
L.append(temp)
left+=1
right-=1
while left
< right:
left += 1
if nums[left] > nums[left - 1]: break
else:
while left < right:
right -= 1
if nums[right] < nums[right + 1]: break
return L
4.Result:
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

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