给你一个由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 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

解题思路

这一题就是之前三数之和的进阶版本，解题的大体思路都是差不多的，只需要先将数组排序，然后固定住两个数，剩余两个数设置为left和right，根据结果的大小来决定是移动左边还是右边。

按照以下的步骤来判断:

  1. 如果数组长度小于4，那么无法组成四数之和，那么直接返回空数组
  2. 将数组进行从小到大的排序
  3. 固定第一个数i，如果i和i-1一样的话，就跳过重复的数
  4. 如果i,i+1,i+2,i+3之和大于目标值的话，那么就结束，因为最小值已经大于目标值了
  5. 如果i,length-3,length-2,lenght-1之和小于目标值的话，那么就结束，因为最大值已经小于目标值了
  6. 目标值处于最大最小值之间，那么再固定一个数j，重复3-4步骤
  7. 此时目标值仍旧处于最大最小值之间，那么设置left为j+1，设置right为length-1，
  8. 根据和与目标值的大小关系进行调整，如果大于那么right--，如果小于那么left++
  9. 循环直至结束

代码

var fourSum = function(nums, target) {
    const quadruplets = [];
    //如果数组长度小于4，那么无法组成四数之和，那么直接返回空数组
    if (nums.length < 4) {
        return quadruplets;
    }
    //将数组进行从小到大的排序
    nums.sort((x, y) => x - y);
    const length = nums.length;
    //固定第一个数
    for (let i = 0; i < length - 3; i++) {
        //如果i 和 i-1 一样的话，那么就跳过重复的数
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        //i + (i+1) + (i+2) + (i+3) 大于目标值的话，就直接结束
        //因为最小值已经大于目标值，后面的数更大，已经没有必要循环了
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break;
        }
        //i + (length-3) + (length-2) + (length-1) 小于目标值的话，就直接结束
        //因为最大值已经小于目标值，后面的数更小，已经没有必要循环了
        if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
            continue;
        }
        //再固定一个数j
        for (let j = i + 1; j < length - 2; j++) {
            //重复上面的步骤，把一些可以提前结束的步骤进行判断
            if (j > i + 1 && nums[j] === nums[j - 1]) {
                continue;
            }
            if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break;
            }
            if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                continue;
            }
            //设置left为j+1，设置right为length-1
            let left = j + 1, right = length - 1;
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                //判断和与目标值的大小关系
                if (sum === target) {
                    quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);
                    while (left < right && nums[left] === nums[left + 1]) {
                        left++;
                    }
                    left++;
                    while (left < right && nums[right] === nums[right - 1]) {
                        right--;
                    }
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return quadruplets;
};