Description
Solution
O(N^2) (排除后做法)
class Solution:
def twoSum(self,nums,start, target):
end = len(nums)-1
while start < end:
if nums[start] + nums[end] > target:
end-=1
elif nums[start] + nums[end] < target:
start+=1
else:
self.res.append([-target,nums[start],nums[end]])
while start < end and nums[start]==nums[start+1]: ####去重重要的方法
start+=1
while start < end and nums[end]==nums[end-1]: ####去重重要的方法
end-=1
start+=1
end -=1
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
self.res=[]
i=0
for i in range(0,len(nums)-2): ####
if i and nums[i-1] == nums[i]: #### Important
continue
target = - nums[i]
self.twoSum(nums,i+1,target)
return self.res
如果不使用sort,纯粹dict做O(N^2):
class Solution:
def twoSum(self,nums,target):
for k in self.ndict.keys():
if self.ndict[k] == 0:
continue
if target - k in self.ndict:
if self.ndict[target - k] == 0:
continue
if k == target -k:
if self.ndict[k]>=2:
min_v = min(min(-target,k),target-k)
max_v = max(max(-target,k),target-k)
self.res.add((min_v,max_v))
else:
min_v = min(min(-target,k),target-k)
max_v = max(max(-target,k),target-k)
self.res.add((min_v,max_v))
def threeSum(self, nums: List[int]) -> List[List[int]]:
self.ndict={}
for num in nums:
if num not in self.ndict:
self.ndict[num]=1
else:
self.ndict[num]+=1
self.res=set()
for k in self.ndict.keys():
target = - k
self.ndict[k]-=1
self.twoSum(nums,target)
self.ndict[k]+=1
return [[0-s[0]-s[1],s[0],s[1]] for s in self.res]
Two Sum with one pass
class Solution:
def twoSum(self, N: List[int], t: int) -> List[int]:
D = {}
for i,n in enumerate(N):
if n not in D: D[n] = i
x = t - n
if x in D and D[x] != i: return [i,D[x]]
```
网友评论