Simple Python solution that beats 90%


  • 0
    M

    Basic idea here is change the problem into pick one number, and find two other numbers that adds up to the inverse of the first number.

    class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            nums.sort()
            runner = 0
            results = []
    
            while runner < len(nums) and nums[runner] <= 0:
                results += self.twoSum(0 - nums[runner], nums[runner + 1:])
                while runner + 1 < len(nums) and nums[runner + 1] == nums[runner]:
                    runner += 1
                runner += 1
            
            return results
    
        def twoSum(self, target, nums):
            left = 0
            right = len(nums) - 1
            results = []
            while left < right:
                if nums[left] + nums[right] == target:
                    results.append([0 - target, nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                elif nums[left] + nums[right] < target:
                    left += 1
                else:
                    right -= 1
            return results
    

Log in to reply
 

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