python四数之和

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

链接：https://leetcode-cn.com/problems/4sum

第一种写法充分利用了python的数据类型dict,set,tuple

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        d={}
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                d.setdefault(nums[i]+nums[j],[]).append((i,j))
        result=set()
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                for a,b in d.get(target-nums[i]-nums[j],[]):
                    temp={i,j,a,b}
                    if len(temp)==4:
                        result.add(tuple(sorted(nums[t] for t in temp)))
        return result

第二种写法采用了双指针的思想

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        result = []
        nums.sort()
        if len(nums) < 4:
            return []
        for i in range(n-3):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            for j in range(i+1, n-2):
                if j > i+1 and nums[j] == nums[j-1]: # 比较第二个数与前一个数是否相同,注意j>i+1
                    continue
                m = j+1
                k = n-1
                while m < k:
                    sums = nums[i] + nums[j] + nums[m] + nums[k]
                    if sums < target:
                        m += 1
                    elif sums == target:
                        result.append([nums[i], nums[j], nums[m], nums[k]])
                        while m < k and nums[m] == nums[m+1]:
                            m += 1
                        while m < k and nums[k] == nums[k-1]:
                            k -= 1
                        m += 1
                        k -= 1
                    else:
                        k -= 1
        return result