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]]
            
        ```