描述

给定一个包含 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类似，在外部增加一个循环即可，依然是变为2Sum的问题

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        if len(nums)<=3:return [] 
        nums.sort()
        result = []
        for a in range(len(nums)-3):
            if a>0 and nums[a]==nums[a-1]:continue
            for b in range(a+1,len(nums)-2):
                if b>a+1 and nums[b]==nums[b-1]:continue
                newtarget = target-(nums[a]+nums[b])
                left,right = b+1,len(nums)-1
                while left<right:
                    if nums[left]+nums[right]==newtarget:
                        result.append([nums[a],nums[b],nums[left],nums[right]])
                        left += 1
                        while left < right and nums[left] == nums[left-1]:
                            left += 1                        
                    if nums[left]+nums[right]<newtarget:
                        left+=1
                    else:
                        right-=1
        return result 

适用于NSum的代码

def fourSum(self, nums, target):
    def findNsum(l, r, target, N, result, results):
        if r-l+1 < N or N < 2 or target < nums[l]*N or target > nums[r]*N:  # early termination
            return
        if N == 2: # two pointers solve sorted 2-sum problem
            while l < r:
                s = nums[l] + nums[r]
                if s == target:
                    results.append(result + [nums[l], nums[r]])
                    l += 1
                    while l < r and nums[l] == nums[l-1]:
                        l += 1
                elif s < target:
                    l += 1
                else:
                    r -= 1
        else: # recursively reduce N
            for i in range(l, r+1):
                if i == l or (i > l and nums[i-1] != nums[i]):
                    findNsum(i+1, r, target-nums[i], N-1, result+[nums[i]], results)

    nums.sort()
    results = []
    findNsum(0, len(nums)-1, target, 4, [], results)
    return results