写点什么

LeetCode 题解:18. 四数之和,哈希表,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 12 月 19 日
LeetCode题解:18. 四数之和,哈希表,JavaScript,详细注释

原题连接:https://leetcode-cn.com/problems/4sum/



解题思路:



  1. 该题是15. 三数之和的进阶版,如果你对三数之和不熟悉,可以先参考我的题解[LeetCode题解:15. 三数之和,JavaScript双循环+HashMap,详细注释](https://leetcode-cn.com/problems/3sum/solution/shuang-xun-huan-mapbao-li-qiu-jie-by-18559231815/)。

  2. 使用哈希表,可以在一次循环中,找到两数之和,可以参考LeetCode题解:1. 两数之和,JavaScript,HashMap单次遍历,详细注释。具体做法是在遍历时,缓存当前值与结果之差,例如map.set(target - nums[i], nums[i]),如果之后遍历时碰到一个值已被缓存,即可提取出之前缓存的值nums[i]

  3. 利用两次循环,分别找到四元组集合的前两个值,再用哈希表找到后两个值,即可组成相应结果。

  4. 去重的大原则是将数组排序,这样相同的值就排列在一起,只要第一个值已被使用过,就可以认为它对应的结果已被生成,这样只要通过nums[i] === nums[i - 1]即可排除掉相等的值。

  5. 由于数组已被排序过,那么四元组也是以此生成的,每找到一个新的四元组,可以对比其和result中的最后一个四元组是否相等,如果相等则不存入result

  6. 需要注意的测试用例:

[0,0,0,0]
0



[-5,5,4,-3,0,0,4,-2]
4



/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
// 去重时要对比前后两个值是否相等,排序保证对比能正常生效
nums.sort((a, b) => a - b);
// 存储结果
let result = [];
for (let i = 0; i < nums.length - 3; i++) {
// 如果有连续数个值相等,在第一遍循环中,第一个值对应的可能解都已被生成过,之后的值都可以跳过
if (nums[i] === nums[i - 1]) {
continue;
}
// 缓存第一级的target,提供给下一层循环使用
let firstTarget = target - nums[i];
for (let j = i + 1; j < nums.length - 2; j++) {
// 如果有连续数个值相等,在当前循环中,先保证第一个值的解会被生成,之后的值都可以跳过
if (j > i + 1 && nums[j] === nums[j - 1]) {
continue;
}
// 缓存第二级的target,提供给下一层循环使用
let secondTarget = firstTarget - nums[j];
// 使用Map缓存最后一层循环的结果,加速查找过程
let map = new Map();
for (let k = j + 1; k < nums.length; k++) {
// 缓存最后一个结果的索引
let lastResult = result.length - 1;
// 由于数组已排序,当前生成的结果只可能与result中的最后一个结果重复,因此需要判断去重
if (result.length) {
if (
result[lastResult][0] === nums[i] &&
result[lastResult][1] === nums[j] &&
result[lastResult][2] === map.get(nums[k]) &&
result[lastResult][3] === nums[k]
) {
continue;
}
}
// 如果当前值存在于Map中,说明找到了匹配的结果
if (map.has(nums[k])) {
result.push([nums[i], nums[j], map.get(nums[k]), nums[k]]);
}
// 将secondTarget与当前值之差缓存在Map中
// 如果之后的遍历中遇到secondTarget - nums[k],就表示找到了两个和为secondTarget的值
// 加上nums[i]和nums[j],就组成了一个结果
map.set(secondTarget - nums[k], nums[k]);
}
}
}
return result;
};



发布于: 2020 年 12 月 19 日阅读数: 12
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:18. 四数之和,哈希表,JavaScript,详细注释