原题地址：四数之和
给定一个包含 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]
]
暴力解法
本题是 三数之和 的进一步扩展，所以解法也是一样的：
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
const fourSum1 = function(nums, target) {
let set = new Set();
for (let i = 0; i < nums.length - 3; i ++) {
for (let j = i + 1; j < nums.length - 2;j ++) {
for (let k = j + 1; k < nums.length - 1; k ++) {
for (let l = k + 1; l < nums.length; l ++) {
if (nums[i] + nums[j] + nums[k] + nums[l] === target) {
// 利用set去重，注意要排序并转为字符串
set.add([nums[i], nums[j], nums[k], nums[l]].sort((a, b) => a - b).toString())
}
}
}
}
}
// 重新转为数组
return [...set].map(item => item.split(',').map(str => parseInt(str, 10)));
};
测试：
let start = new Date();
const test = fourSum1;
console.log(test([1, 0, -1, 0, -2, 2], 0)); // [ [ -1, 0, 0, 1 ], [ -2, -1, 1, 2 ], [ -2, 0, 0, 2 ] ]
console.log(new Date().getTime() - start.getTime()); // 7
时间复杂度： 四重遍历，时间复杂度为O($n^4$)
空间复杂度： 空间复杂度为O($n^3$)
双指针法
跟三数之和一样，本题也可以采用又指针法，不过由于需要计算4个数的和，所以要先固定两个数：
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
const fourSum2 = function(nums, target) {
nums = nums.sort((a, b) => a - b);
let result = [];
// 固定一个数，找出另外三个符合条件的数
for (let i = 0; i < nums.length - 3; i ++) {
// 因为不能有重复结果，所以需要跳过重复数据
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
// 和已经大于target，不可能再满足条件
if (nums[i] * 4 > target) {
break;
}
// 再固定一个数
for (let j = i + 1; j < nums.length - 2; j ++) {
if (j > i + 1 && nums[j] === nums[j - 1]) {
continue;
}
if (nums[i] + nums[j] * 3 > target) {
break;
}
// 双指针，初始分别在两端
let [left, right] = [j + 1, nums.length - 1];
while (left < right) {
if (nums[left] + nums[right] + nums[i] + nums[j] < target) {
left ++; // 和小于target就让左指针右移
} else if (nums[left] + nums[right] + nums[i] + nums[j] > target) {
right --; // 大于target则让右指针左移
} else {
// 找到了符合条件的元组
result.push([nums[i], nums[j], nums[left], nums[right]]);
left ++;
right --;
// 跳过重复数据
while (left < right && nums[left] === nums[left - 1]) {
left ++;
}
while (left < right && nums[right] === nums[right + 1]) {
right --;
}
}
}
}
}
return result;
};
测试：
let start = new Date();
const test = fourSum2;
console.log(test([1, 0, -1, 0, -2, 2], 0)); // [ [ -2, -1, 1, 2 ], [ -2, 0, 0, 2 ], [ -1, 0, 0, 1 ] ]
console.log(new Date().getTime() - start.getTime()); // 5
时间复杂度： 时间复杂度为O($n^3$)
空间复杂度： 空间复杂度为O($n^3$)
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 28,2019