Simple short python sol.


  • 0
    0

    but the run time is slow, 564 ms. plz tell me how to improve! thx

    def twoSum(self, nums, target):
        sol = set()
        n_set = set()
        for num in nums:
            if num in n_set:
                tup = tuple( sorted([num, target-num, -target]) )
                sol.add(tup)
            n_set.add(target - num)
        
        return sol
    
    def threeSum(self, nums):
        sol = set()
        for i, n in enumerate(nums):
            sol = sol.union( self.twoSum(nums[i+1:], -n) )
    
        return list(sol)

  • 0
    X

    348ms, a bit better. But still not enough.

    class Solution(object):
        def twoSum(self,target, nums):
            h={}
            result = set()
            for i,nums in enumerate(nums):
                if target-nums in h :
                    result.add(tuple(sorted([-target,nums,target - nums])))
                h[nums] = i
            return result
    
    
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            visited = {}
            result = set()
            for i, n in enumerate(nums):
                if nums[i] not in visited:
                   result = result.union(self.twoSum(-n, nums[i+1:]))
                   visited[nums[i]]=1
            return list(result)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.