18

# class Solution:
#     def fourSum(self, nums, target):
#         """
#         :type nums: List[int]
#         :type target: int
#         :rtype: List[List[int]]
#         """
#         '''
#         四数和，与三数和类似，可见第15题
#         '''
#         res = []
#         if not nums:
#             return res
#         nums.sort()
#         len_nums = len(nums)
#         for i in range(len_nums - 3):
#             if i > 0 and nums[i] == nums[i - 1]:
#                 continue
#             for j in range(i+1, len_nums - 2):
#                 if j > i+1 and nums[j] == nums[j - 1]:
#                     continue
#                 l = j + 1
#                 r = len_nums - 1
#                 while l < r:
#                     if nums[i] + nums[j] + nums[l] + nums[r] == target:
#                         res.append([nums[i], nums[j], nums[l], nums[r]])
#                         while l < r and nums[l] == nums[l+1]:
#                             l += 1
#                         while l < r and nums[r] == nums[r-1]:
#                             r -= 1
#                         l += 1
#                         r -= 1
#                     elif nums[i] + nums[j] + nums[l] + nums[r] < target:
#                         l += 1
#                     else:
#                         r -= 1
#         return res


class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        '''
        四数和，与三数和类似，可见第15题
        '''
        res = []
        if not nums:
            return res
        nums.sort()
        len_nums = len(nums)
        for i in range(len_nums - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i+1, len_nums - 2):
                if j > i+1 and nums[j] == nums[j - 1]:
                    continue
                dic = dict()
                for e in nums[j+1:]:
                    if e not in dic:
                        dic[target-nums[i]-nums[j]-e] = 1
                    else:
                        if dic[e] != 0:
                            res.append([nums[i], nums[j], target - nums[i] - nums[j] - e, e])
                            dic[e] = 0
        return res


if __name__ == "__main__":
    solve = Solution()
    print(solve.fourSum([1, 0, -1, 0, -2, 2], 0))