18. 四数之和（中）

• 题目
• 题解：排序+双指针

题目

• 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
  0 <= a, b, c, d < n
  a、b、c 和 d 互不相同
  nums[a] + nums[b] + nums[c] + nums[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 = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

题解：排序+双指针

• 沿用三数之和的代码，在外部多加一个for循环控制多加的一个数，剪枝操作不合适容易把正确结果剪去。

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        res = []# 存储符合条件的四元组
        nums.sort()# 对数组进行排序，方便后续处理
        for j in range(len(nums)):
            if nums[j] > 0 and target > 0 and nums[j] > target:#剪枝
                return res
            if j > 0 and nums[j] == nums[j - 1]:#去重
                continue
            for i in range(j + 1, len(nums)):
                # if nums[i] > 0 and target > 0 and nums[i] > target:#这个地方不能剪枝，比如nums=[-5,5,4,-3,0,0,4,-2]target=4在[-5,0,4,5]就返回了，会漏掉[-3,-2,4,5]结果
                #     return res
                if i > j + 1 and nums[i] == nums[i - 1]:#去重
                    continue

                left = i + 1#初始化指针left
                right = len(nums) - 1#初始化指针right

                while left < right:
                    Sum = nums[i] + nums[left] + nums[right] + nums[j]
                    if Sum == target:#找到符合条件的值
                        res.append([nums[j], nums[i], nums[left], nums[right]])#加入结果集
                        while left < right and nums[left] == nums[left + 1]:#去重
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:#去重
                            right -= 1
                        left += 1#遇到满足条件的值后指针移动
                        right -= 1
                    elif Sum > target:#没遇到满足条件的值，判断Sum与target大小移动指针
                        right -= 1
                    else:
                        left += 1
        return res