Readable Python solution with comments [230ms]


  • 0
    class Solution(object):
        def fourSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            # Collect list of number pairs by their sum
            count = len(nums)
            pairsMap = {}
            for i in xrange(count - 1):
                for j in xrange(i + 1, count):
                    s = nums[i] + nums[j] 
                    if s not in pairsMap:
                        pairsMap[s] = []
                    pairsMap[s].append((i, j))
                    
            # Find pairs summing up to the target
            results = set()
            for s, pairs1 in pairsMap.iteritems():
                
                # Find matching pairs to sum up to target
                delta = target - s
                pairs2 = pairsMap.get(delta)
                if pairs2 is None:
                    continue
                
                # Combine pairs
                for pair1 in pairs1:
                    for pair2 in pairs2:
                        
                        # Exclude pair combinations using overlapping list items
                        i1, j1 = pair1
                        i2, j2 = pair2
                        if i1 in pair2 or j1 in pair2:
                            continue
                        
                        # Keep unique results
                        n1, n2, n3, n4 = sorted((nums[i1], nums[j1], nums[i2], nums[j2]))
                        results.add((n1, n2, n3, n4))
                        
            return list(results)
    

Log in to reply
 

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