Readable Python solution [1300ms]


  • 0
    class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
    
            Time: O(n**2)
            Space: O(n)
            
            """
            # Sort numbers in place
            # Time: O(n * log(n))
            # Space: O(1)
            nums.sort()
    
            # Deduplicate results by collecting them in a set
            # Space: O(n)
            triplets = set()
    
            # For each possible a try to find (b, c) to sum up to zero
            # Holds: i < j < k and a <= b <= c
            # Time: O(n**2)
            count = len(nums)
            for i, a in enumerate(nums):
                
                # Try to find suitable b and c by bidirectional search
                j = i + 1
                k = count - 1
                while j < k:
                    s = a + nums[j] + nums[k]
                    if s < 0:
                        j += 1
                    elif s > 0:
                        k -= 1
                    else:
                        # Found
                        b = nums[j]
                        c = nums[k]
      
                        # No need to sort, since a <= b <= c
                        triplets.add((a, b, c))
                        
                        # Skip until we get a different solution
                        # (optimisation required to stay under time limit with an input causing many duplicate solutions)
                        j += 1
                        while j < k and nums[j] == b:
                            j += 1
    
            return list(triplets)
    

Log in to reply
 

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