LeetCode 题解:18. 四数之和,哈希表,JavaScript,详细注释
原题连接:https://leetcode-cn.com/problems/4sum/
解题思路:
该题是15. 三数之和的进阶版,如果你对三数之和不熟悉,可以先参考我的题解[LeetCode题解:15. 三数之和,JavaScript双循环+HashMap,详细注释](https://leetcode-cn.com/problems/3sum/solution/shuang-xun-huan-mapbao-li-qiu-jie-by-18559231815/)。
使用哈希表,可以在一次循环中,找到两数之和,可以参考LeetCode题解:1. 两数之和,JavaScript,HashMap单次遍历,详细注释。具体做法是在遍历时,缓存当前值与结果之差,例如
map.set(target - nums[i], nums[i])
,如果之后遍历时碰到一个值已被缓存,即可提取出之前缓存的值nums[i]
。利用两次循环,分别找到四元组集合的前两个值,再用哈希表找到后两个值,即可组成相应结果。
去重的大原则是将数组排序,这样相同的值就排列在一起,只要第一个值已被使用过,就可以认为它对应的结果已被生成,这样只要通过
nums[i] === nums[i - 1]
即可排除掉相等的值。由于数组已被排序过,那么四元组也是以此生成的,每找到一个新的四元组,可以对比其和
result
中的最后一个四元组是否相等,如果相等则不存入result
。需要注意的测试用例:
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/36005665375994cbf03945da6】。文章转载请联系作者。
评论