Fast python solution using two hash sets


  • 0

    The idea is to use the first set to store all the numbers and the second set to store the numbers having duplicates. The fist set was used to generate a sorted list containing all the distinct numbers. Pick two distinct numbers from the sorted list and calculate the third one. If the third number is greater than the second one, check the first set. Otherwise, if the third number equals to the first one or the second one, check the duplicate set.

    class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            result = []
            numSet = set()
            duplicateSet = set()
            zeroCounts = 0
            for n in nums:
                if n not in numSet:
                    numSet.add(n)
                else:
                    duplicateSet.add(n)
                if not n:
                    zeroCounts += 1
            if zeroCounts >= 3:
                result.append([0, 0 ,0])
            sortedNums = sorted(list(numSet))
            
            for i in range(len(sortedNums)-1):
                n1 = sortedNums[i]
                if n1 >= 0:
                    return result
                for j in range(i+1, len(sortedNums)):
                    n2 = sortedNums[j]
                    n3 = -(n1 + n2)
                    if n3 > n2:
                        if n3 in numSet:
                            result.append([n1, n2, n3])
                    elif n3 == n1 and n1 in duplicateSet or n3 == n2 and n2 in duplicateSet:
                        result.append([n1, n3, n2])
                    
            return result
    

Log in to reply
 

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