Python solution with 2 twoSums (with hashtable)


  • 0
    S

    Just get all possible twoSums result and store them in a hash able.
    Then do a "twoSums" to this hash table.
    Pay attention to the overlappings.

    """
    class Solution(object):

    def fourSum(self, nums, target):
    
        if len(nums) < 4:
            return []
        hashtable = {}
        l = len(nums)
        for i in range(l):
            for j in range(i+1, l):
                if nums[i] + nums[j] not in hashtable:
                    hashtable[nums[i] + nums[j]] = [[i,j]]
                else:
                    hashtable[nums[i] + nums[j]].append([i, j])
        sort_key = sorted(hashtable.keys())
        # print hashtable
        left,right = 0, len(sort_key)-1
        result = []
        while left <= right:
            if sort_key[left] + sort_key[right] == target:
                print left, right
                for item_1 in hashtable[sort_key[left]]:
                    for item_2 in hashtable[sort_key[right]]:
                        # print item_1, item_2
    
                        intersect = set(item_1).intersection(item_2)
                        # print intersect
                        if len(intersect) != 0:
                            continue
                        temp = [nums[c] for c in item_1] + [nums[c] for c in item_2]
                        temp.sort()
                        if temp not in result:
                            result.append(temp)
                left += 1
                right -= 1
            elif sort_key[left] + sort_key[right] < target:
                left += 1
            else:
                right -= 1
        return result
    

    """


Log in to reply
 

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