每日一题：每天一个新挑战；
循序渐进：从易到难，扎实掌握；
系统分类：按数据结构分类，有助于构建知识框架；
丰富题量：100 道精选题，覆盖简单/中等/困难难度。

给你一个由 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
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

代码卡片

题目解析

“四数之和”问题要求找到数组中四个不同元素的组合，使其和等于目标值，并且不能有重复的四元组。由于暴力解法的时间复杂度过高，因此我们需要使用更高效的方法来解决问题。

方法一：排序 + 双指针

排序：首先将数组进行排序，这样可以方便地跳过重复元素，并且简化后续步骤中的双指针操作。
四重循环：使用四重循环，其中外层两个循环固定两个数，内层两个循环使用双指针查找另外两个数，使得四个数的和等于目标值。
跳过重复：为了避免重复结果，我们在每次循环时都要检查当前数字是否和前一个数字相同，如果相同则跳过，以避免产生相同的四元组。

时间复杂度: 排序的时间复杂度为 O(n log n)，四重循环的时间复杂度为 O(n^3)，所以总体的时间复杂度为 O(n^3)。
空间复杂度: 由于只使用了常数级别的额外空间，空间复杂度为 O(1)。

var fourSum = function (nums, target) {
    nums.sort((a, b) => a - b);
    const result = [];
    const n = nums.length;

    for (let i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue; // 跳过重复元素
        for (let j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue; // 跳过重复元素
            let left = j + 1;
            let right = n - 1;
            while (left < right) {
                const sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum === target) {
                    result.push([nums[i], nums[j], nums[left], nums[right]]);
                    while (left < right && nums[left] === nums[left + 1]) left++; // 跳过重复元素
                    while (left < right && nums[right] === nums[right - 1]) right--; // 跳过重复元素
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return result;
}

方法二：哈希表

使用哈希表存储数组中的元素及其下标，利用两数之和的思路，将问题转化为查找剩余两数之和等于 target – 当前两数之和的问题。

var fourSum = function (nums, target) {
    nums.sort((a, b) => a - b);
    const result = [];
    const n = nums.length;

    for (let i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        for (let j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            const hashMap = new Map();
            for (let k = j + 1; k < n; k++) {
                const complement = target - nums[i] - nums[j] - nums[k];
                if (hashMap.has(complement)) {
                    result.push([nums[i], nums[j], complement, nums[k]]);
                    while (k + 1 < n && nums[k] === nums[k + 1]) k++;
                }
                hashMap.set(nums[k], k);
            }
        }
    }
    return result;
}