leetcode18. 四数之和

给定一个包含 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]
]

#python 完全利用3sum,时间不理想
class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        for idx,val in enumerate(nums):
            if idx>=1 and val == nums[idx-1]:
                continue
            target_three_sum = target-val
            res.append(self.threesum(val, nums[idx+1:],target_three_sum,res))
            res.remove(None)
        return res



    def threesum(self, prefix, nums, target, res):
        # nums.sort()
        for idx,val in enumerate(nums):
            if idx>=1 and val == nums[idx-1]:
                continue
            # 思想：有没有人正在找我？没有的话，我就去找我想找的人。
            wanted_pairs = {} # 想找的人
            temp=None
            for pair in nums[idx+1:]:
                if pair==temp:
                    continue
                if pair not in wanted_pairs: # Not他们想找的人,then加入他们去找我想找的人
                    wanted_pairs[target - val - pair]=1
                else:
                    res.append([prefix,val,pair,target - val - pair]) # 我就是他们中那个谁想找的人
                    temp=pair