18. 四数之和

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

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

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [], target = 0
输出：[]

提示：

• 0 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

Python 解答：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                k, s = j+1, len(nums)-1
                while k < s:
                    if nums[i]+nums[j]+nums[k]+nums[s] > target:
                        s -= 1
                    elif nums[i]+nums[j]+nums[k]+nums[s] < target:
                        k += 1
                    else:
                        if [nums[i], nums[j], nums[k], nums[s]] not in res:
                            res.append([nums[i], nums[j], nums[k], nums[s]])
                        s -= 1
                        k += 1
        return res