3Sum solutions Python


  • 0
    D
    class Solution:
        def twoSum(self, nums, target):
            outputs = []
            dic = {}
            found = False
            for idx, num  in enumerate(nums):
                dic[num] = idx
                
            for idx, num in enumerate(nums):
                if idx != 0  and num == nums[idx-1]:
                    continue
                
                t = target - num
                
                if t in dic and dic[t] > idx:
                    found = True
                    outputs.append([idx, dic[t]])
            
            if not found:
                return None
            
            return outputs
        
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            #makre sure have enough numbers
            numbers = nums
            if len(numbers) < 3:
                return []
            
            numbers.sort()
            results = []
            
            for idx, num in enumerate(numbers):
                if num > 0: # after sorted, the smallest should < 0
                    continue
                if idx != 0 and num == numbers[idx-1]:
                    continue
                    
                target = 0-num
                # look at all afterward elements
                twosum = self.twoSum(numbers[idx+1:], target)
                if twosum:
                    for comb in twosum:
                        result = [numbers[idx], numbers[comb[0]+idx+1], numbers[comb[1]+idx+1]]
                        result.sort()
                        results.append(result)
            
            return results
    

Log in to reply
 

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