(Medium #18) 4Sum

Problem

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

My solution

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
                
        if len(nums) < 4:
            return []
        
        out = []        
        for i in range(len(nums)):            
            if i > 0 and nums[i] == nums[i-1]:
                continue
            
            choice1 = nums[i]
            for k in range(i+1, len(nums)):
                if k > i+1 and nums[k] == nums[k-1]:
                    continue
                choice2 = nums[k]
                
                start = k+1
                end = len(nums)-1
                
                while start < end:
                    choice3 = nums[start]
                    choice4 = nums[end]
                    
                    if choice1 + choice2 + choice3 + choice4 == target:
                        out.append([choice1, choice2, choice3, choice4])
                        start += 1
                        end -= 1                        
                        while start < end and nums[start] == nums[start-1]:
                            start += 1
                        while start < end and nums[end] == nums[end+1]:
                            end -= 1
                    elif choice1 + choice2 + choice3 + choice4 < target:
                        start += 1
                        while start < end and nums[start] == nums[start-1]:
                            start += 1
                    else:# choice1 + choice2 + choice3 + choice4 > target
                        end -= 1
                        while start < end and nums[end] == nums[end+1]:
                            end -= 1
        
        return out

Runtime: 1724ms, Memory: 13.8MB

Other people solution

class Solution:
    def fourSum(self, nums, target):
        l = len(nums)
        d = {}
        res = set()
        nums.sort()
        for i in range(l - 1):
            for j in range(i + 1, l):
                key = nums[i] + nums[j]
                if key not in d:
                    d[key] = [(i, j)]
                else:
                    d[key].append((i, j))
        for i in range(2, l - 1):
            for j in range(i + 1, l):
                pre = target - nums[i] - nums[j]
                if pre in d:
                    for v in d[pre]:
                        if v[1] < i:
                            res.add((nums[v[0]], nums[v[1]], nums[i], nums[j]))
        return [list(i) for i in res]

Runtime: 132ms, Memory: 17.6MB