A fast and straightforward python solution (192ms) with explanations

  • 2
    def threeSum(self, nums):
        count={} # number: count
        for i in nums:
            count[i] = count.get(i,0) + 1
        ans = []
        nsort = sorted(count.keys())
        for i in xrange(len(nsort)):
            n1 = nsort[i]
            count[n1] -= 1
            for j in xrange(i,len(nsort)):
                n2 = nsort[j]
                if count[n2] >= 1:
                    count[n2] -= 1
                    n3 = - (n1 + n2)
                    if n3>=n2 and n3 in count and count[n3]>=1:
                        ans.append([n1, n2, n3])
        return ans


    1. use a dictionary to count the frequency of the numbers in the input array
    2. sort the keys of the dictionary (i.e. unique numbers in the input array)
    3. iterate over the sorted numbers (first loop): n1
    4. iterate over the sorted numbers that are equal to or larger than num1 (second loop): n2.
    5. check if n3 (n3 = -(n1+n2), n3>=n2) is in count. If so, append [n1, n2, n3] to the answer list.

    Note: we subtract the count by 1 in the beginning of loop 1, and add it back at the end of the loop. We use a similar approach for loop 2, but we first check if count[n2]>=1 because in the case of n2==n1, count[n2] could be 0.
    Also, since we already sort the keys (unique numbers) in the beginning, in step 4 and 5 we only have to check the numbers that are equal to or larger than the number in the current loop. By doing so, we reduce the number of loops (from n^2 to n(n+1)/2, where n is the amount of the unique numbers), avoid duplicate triplets, and do not have to sort the triplets again.

Log in to reply

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