Буквенный код 18: 4Sum

Бит-код 18: 4Sum

Имея массив S из n целых чисел, существуют ли элементы a, b, c и d в S такие, что a + b + c + d = target? Найдите все уникальные четверки в массиве, который дает сумму цели.

Примечание. В наборе решений не должно быть повторяющихся четверок.

Например, задан массив S = [1, 0, -1, 0, -2, 2] и цель = 0.

Набор решений:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[- 2, 0, 0, 2]
]

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        n = len(nums)
        res = []
        if n < 4:
            return res
        
        nums.sort()
        
        for i in range(0, n-3):
            print i
            if i == 0 or nums[i] != nums[i-1]:
                for j in range(i+1, n-2):
                    if nums[j] != nums[j-1]:
                        k = j + 1
                        l = n - 1
                        
                        while k < l:
                            sum = nums[i] + nums[j] + 
                            nums[k] + nums[l]
                            if sum == target:
                                res.append([nums[i], 
                                            nums[j], 
                                            nums[k], 
                                            nums[l]])
                                
                                while k < l and \
                                        nums[k] == nums[k+1]:
                                    k += 1
                                while k < l and \
                                        nums[l] == nums[l -1]:
                                    l -= 1
                            
                            elif sum < 0:
                                k += 1
                            else:
                                l -= 1
        return res