Python solution using sum of all pair (not sure about time complexity)


  • 0
    A

    Here's my solution. I calculated all the sum of pairs but I am not sure about the time complexity.

    from collections import defaultdict
    class Solution:
    # @param {integer[]} nums
    # @param {integer} target
    # @return {integer[][]}
    def fourSum(self, nums, target):
        pair = defaultdict(set)
        count = {}
        nums.sort()
        
        for n in nums:
            if n not in count:
                count[n] = 0
            count[n] += 1
        
        for i in xrange(len(nums)-1):
            for j in xrange(i+1, len(nums)):
                tmp = nums[i] + nums[j]
                pair[tmp].add((nums[i], nums[j])) #unique pair
        
        ans = set()
        for i in xrange(len(nums)-3):
            for j in xrange(i+1, len(nums)-2):
                count[nums[i]] -= 1
                count[nums[j]] -= 1
                aim = target-nums[i]-nums[j]
                
                if aim in pair:
                    for (v1, v2) in pair[aim]:
                        if v1 < nums[j] or v2 < nums[j]:
                            continue
                        count[v1] -= 1
                        count[v2] -= 1
                        if count[v1] >= 0 and count[v2] >= 0:
                            ans.add((nums[i], nums[j], v1, v2))
                            
                        count[v1] += 1
                        count[v2] += 1
                
                count[nums[i]] += 1
                count[nums[j]] += 1
        
        return list(ans)

Log in to reply
 

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