给你一个由 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]]

    1. /**
    2.  * @param {number[]} nums
    3.  * @param {number} target
    4.  * @return {number[][]}
    5.  */
    6. var fourSum = function (nums, target) {
    7.     // 简化成2数之和，双指针解法
    8.     // 先排序
    9.     nums.sort((a, b) => a - b);
    11.     const nSum = (nums, n, start, target) => {
    12.         let res = [];
    13.         let length = nums.length;
    14.         // 小于二没意义，当然这里不需要加
    15.         if (n < 2 || length < n) return res;
    16.         // 初始化 基础两数之和
    17.         if (n === 2) {
    18.             let l = start, r = length - 1;
    19.             while (l < r) {
    20.                 // 储存第一次出现值
    21.                 let left = nums[l], right = nums[r];
    22.                 let sum = left + right;
    23.                 if (sum < target) {
    24.                     while (l < r && left === nums[l]) l++;
    25.                 } else if (sum > target) {
    26.                     while (l < r && right === nums[r]) r--;
    27.                 } else {
    28.                     res.push([left, right]);
    29.                     while (l < r && left === nums[l]) l++;
    30.                     while (l < r && right === nums[r]) r--;
    31.                 }
    32.             }
    33.         } else {
    34.             // 处理多数时
    35.             for (let i = start; i < length; i += 1) {
    36.                 // 这里递归赋值转两数之和
    37.                 let sub = nSum(nums, n - 1, i + 1, target - nums[i]);
    39.                 // 取返回res
    40.                 for (let arr of sub) {
    41.                     // 合并进res
    42.                     res.push([...arr, nums[i]])
    43.                 }
    44.                 // 跳过重复
    45.                 while (i < length - 1 && nums[i] === nums[i + 1]) i += 1
    46.             }
    47.         }
    48.         return res;
    49.     }
    51.     return nSum(nums, 4, 0, target)
    52. };

    image.png