18. 四数之和

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

思路--双指针

首先判断如果数组为空，或者数字长度小于4，则直接返回空数组。
接着对数组进行排序。
与三数之和类似，需要多加一层循环
遍历数组：
首先，首先固定第一个元素
如果当前的数字和前一个数字相同，那么对于重复元素：直接跳过本次循环，避免出现重复解
接着，固定第二个元素，
同样，如果当前的数字和前一个数字相同，那么对于重复元素：直接跳过本次循环，避免出现重复解
令 c = b + 1，d = len(nums) - 1，当c< d，执行循环：
若nums[a] + nums[b] + nums[c] + nums[d] > target，说明总和太大，d左移
若nums[a] + nums[b] + nums[c] + nums[d] < target，说明总和太小，c 右移
若nums[a] + nums[b] + nums[c] + nums[d] == target，则将当前的元素添加到结果集中，同时执行循环，判断左界和右界是否和下一位置重复，去除重复解，并同时将 c，d移到下一位置，寻找新的解

python3解法

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        if not nums or len(nums) < 4:
            return  []
        nums.sort()
        ans = []
        # 首先固定第一个元素，注意范围边界
        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
                # 双指针确定地3,4个元素，第三个元素是第二个元素的下一个元素，第的哥元素始终从最后一个元素开始遍历
                c = b + 1
                d = len(nums) - 1
                while c < d:
                    if nums[a] + nums[b] + nums[c] + nums[d] > target:
                        d -= 1
                    elif nums[a] + nums[b] + nums[c] + nums[d] < target:
                        c += 1
                    else:
                        ans.append([nums[a], nums[b], nums[c], nums[d]])
                        # 右移指针，确保跳过重复元素
                        while c < d and nums[c] == nums[c + 1]:
                            c += 1
                        # 左移指针，确保跳过重复元素
                        while c < d and nums[d] == nums[d - 1]:
                            d -= 1
                        c += 1
                        d -= 1
        return ans

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。