Python - A generalization from 2Sum ad 3Sum


  • 0
    J
    class Solution(object):
    
        def fourSum(self,nums,target):
            solution2 = []
            solution3=[]
            solution = []
            nums.sort()
            for ai,a in enumerate(nums):
                if ai > 0 and a == nums[ai-1]:
                    solution2 = self.two_sum(nums[ai+1:],target-2*a,[a,a])
                    if solution2:solution+=solution2
                else:
                    solution3 = self.three_sum(nums[ai+1:],target-a,[a])
                    if solution3:solution+=solution3
            return solution
    
        def three_sum(self,nums,target,a):
            solution = []
            for idx,tgt in enumerate(nums):
                if idx>0 and nums[idx] == nums[idx-1]:continue
                path = {}
                vist = set()
                for i in xrange(idx+1,len(nums)):
                    if nums[i] not in path:
                        path[target-tgt-nums[i]] = nums[i]
                    elif nums[i] in path and nums[i] not in vist:
                        solution.append(a+[tgt,path[nums[i]],nums[i]])
                        vist.add(nums[i])
            return solution
    
        def two_sum(self,nums, target,b):
            path = {}
            solution = []
            for i in nums:
                if i in path:
                    return solution.append(b+[path[i],i])
                else:
                    path[target-i] = i
            return solution 
    

Log in to reply
 

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