3Sum

作者: Mree111 | 来源:发表于2019-10-20 13:52 被阅读0次

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

    相关文章

      网友评论

          本文标题:3Sum

          本文链接:https://www.haomeiwen.com/subject/ztaomctx.html