18. 四数之和
18. 四数之和
题目
Given an array nums
of n
integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]]
such that:
0 <= a, b, c, d < n
a
,b
,c
, andd
are distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Constraints:
1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
题目大意
给定一个数组,要求在这个数组中找出 4 个数之和为 0 的所有组合。
解题思路
这一题比较麻烦的一点在于,最后输出解的时候,要求输出不重复的解。数组中同一个数字可能出现多次,同一个数字也可能使用多次,但是最后输出解的时候,不能重复。例如 [-1,1,2, -2] 和 [2, -1, -2, 1]、[-2, 2, -1, 1] 这 3 个解是重复的。
和 第 15 题 的解法一致,这一题是第 15 题的升级版,思路都是完全一致的,需要去重和排序。
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
nums = nums.sort((a, b) => a - b);
const len = nums.length;
let res = [];
for (let i = 0; i < len - 3; i++) {
for (let j = i + 1; j < len - 2; j++) {
let left = j + 1;
let right = len - 1;
while (left < right) {
let sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum === target) {
res.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) {
right--;
} else {
left++;
}
}
while (nums[j] === nums[j + 1]) j++;
}
while (nums[i] === nums[i + 1]) i++;
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
1 | 两数之和 | [✓] | 数组 哈希表 | |
15 | 三数之和 | [✓] | 数组 双指针 排序 | |
454 | 四数相加 II | 数组 哈希表 | ||
1995 | 统计特殊四元组 | 数组 哈希表 枚举 |