18. 四数之和

给定一个包含n 个整数的数组nums和一个目标值target，判断nums中是否存在四个元素 a，b，c和 d，使得a + b + c + d的值与target相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：

[

  [-1,  0, 0, 1],

  [-2, -1, 1, 2],

  [-2,  0, 0, 2]

]

class Solution:

    def fourSum(self, nums, target):

        """

        :type nums: List[int]

        :type target: int

        :rtype: List[List[int]]

        """

        res, dicti = set(), {}

        numLen = len(nums)

        nums.sort()

        for i in range(numLen):

            for j in range(i+1, numLen):

                key = nums[i] + nums[j]

                if key not in dicti.keys():

                    dicti[key] = [(i,j)]

                else:

                    dicti[key].append((i,j))

        for i in range(numLen):

            for j in range(i+1, numLen-2):

                exp = target - nums[i] -nums[j]

                if exp in dicti.keys():

                    for tmpIndex in dicti[exp]:

                        if tmpIndex[0] > j:

                            res.add((nums[i], nums[j], nums[tmpIndex[0]], nums[tmpIndex[1]]))

        return [list(i) for i in res]