LeetCode 349. Intersection of Two Arrays 题解哈希表空间换时间求两个数组的交集【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇题解以当前仓库中 problems/349.intersection-of-two-arrays.en.md及其中文版 problems/349.intersection-of-two-arrays.md为核心骨架完整继承题目定义、解题思路、双语言代码与复杂度分析并结合仓库中关于空间换时间算法思想的论述进行源码级扩充。读完本文你将掌握用哈希表在 O(N) 时间内求两数组去重交集的完整套路并能直接迁移到其他去重 快速查找类问题。题目背景与问题定义LeetCode 第 349 题 Intersection of Two Arrays两个数组的交集是一道典型的哈希表入门题被仓库的 README.md 收录在简单难度题单中同时出现在 collections/easy.md 的经典简单题合集里。给定两个数组编写一个函数来计算它们的交集。示例 1输入nums1 [1,2,2,1], nums2 [2,2] 输出[2]示例 2输入nums1 [4,9,5], nums2 [9,4,9,8,4] 输出[9,4]说明题目的两个关键约束输出结果中的每个元素一定是唯一的即结果需要去重可以不考虑输出结果的顺序因此返回[9,4]或[4,9]均为正确答案。从示例 1 可以看出nums1和nums2中都含有重复元素2出现了两次但输出只保留一个2示例 2 中9、4在两个数组中均多次出现输出同样各保留一个。理解结果去重这一约束是设计正确解法的前提。前置知识哈希表与空间换时间本题解要求的前置知识只有一个哈希表hashtable。哈希表以O(1)的平均时间复杂度完成键是否存在的判定与读写。这一点在仓库的 thinkings/README.md 中有明确呼应——该文件将空间换时间列为暴力优化法的核心手段并明确指出其典型载体包括哈希表、前缀树等暴力优化法也是必须掌握的……有剪枝空间换时间等。其中空间换时间又有很多比如哈希表前缀树等等。本仓库中的多道题解都运用了这一思想例如 problems/1.two-sum.md两数之和与 problems/560.subarray-sum-equals-k.md和为 K 的子数组均通过哈希表把暴力枚举的二次复杂度降为线性。理解 349 题等于掌握了这批哈希表题目的最小可运行范本。解题思路两轮遍历 哈希表标记原文档给出的核心思路非常精炼分三步建表先遍历第一个数组nums1把每个元素作为键写入哈希表同时把元素本身作为值见下文误区分析查表再遍历第二个数组nums2如果当前元素在哈希表中存在说明它是交集成员push进结果数组清空标记命中后立即把该键从哈希表中清空置为undefined或pop删除避免nums2中的重复元素被再次计入从而天然满足结果唯一的约束。最后返回结果数组即可。为什么需要清空这一步因为nums2中可能有重复元素如示例 1 的[2,2]。若不清空第二次遇到2时哈希表中仍然存在2会再次push导致输出[2,2]违反结果唯一的约束。清空标记使每个元素在结果中最多出现一次这一约束在遍历过程中自动被满足无需额外的去重集合。为什么先遍历nums1而不是nums2二者在算法上对称选择哪个数组建表都可以。原文档选择先遍历第一个数组建表、再遍历第二个数组查表实现上没有任何区别最终时间复杂度相同。关键点解析空间换时间用一块哈希表的额外空间把判断一个元素是否在另一数组中出现的代价从每次 O(N) 的线性扫描降为 O(1)从而让整体时间复杂度从暴力的 O(N²) 降到 O(N)。这正是 thinkings/README.md 所总结的优化思路在本体的具体化。多语言实现原文档声明代码支持JS、Python两种语言以下代码完整继承自原文档JS 代码中的笔误空格已修正为标准语法可直接运行。Javascript 实现哈希表 双轮遍历/** * param {number[]} nums1 * param {number[]} nums2 * return {number[]} */ var intersection function (nums1, nums2) { const visited {}; const ret []; for (let i 0; i nums1.length; i) { const num nums1[i]; visited[num] num; } for (let i 0; i nums2.length; i) { const num nums2[i]; if (visited[num] ! undefined) { ret.push(num); visited[num] undefined; } } return ret; };Python 实现一哈希表 双轮遍历class Solution: def intersection(self, nums1: List[int], nums2: List[int]) - List[int]: visited, result {}, [] for num in nums1: visited[num] num for num in nums2: if num in visited: result.append(num) visited.pop(num) return resultPython 实现二集合运算一行解原文档同时给出利用 Python 内置集合的极简解法一行完成去重 求交集class Solution: def intersection(self, nums1: List[int], nums2: List[int]) - List[int]: return set(nums1) set(nums2)set()天然去重运算符对两个集合求交集语义与题目输出唯一元素、不考虑顺序的约束完全吻合是最贴近 Python 语言习惯的写法。它同样基于哈希表的 O(1) 查找能力只是把手动建表 手动去重的细节交由语言内置实现完成。复杂度分析设nums1的长度为 N、nums2的长度为 M则时间复杂度O(N M)。两轮遍历各执行一次每个元素只被处理一次哈希表的读写均为 O(1)。原文档简记为 O(N)。空间复杂度O(N)。visited哈希表的大小取决于nums1去重后的元素个数最坏情况下为 O(N)结果数组ret不计入辅助空间或最多 O(min(N,M))。相比之下朴素的暴力解法对nums2的每个元素线性扫描nums1时间复杂度为 O(N·M)且还需要额外的去重处理。哈希表解法以 O(N) 的额外空间换取了一个数量级的时间收益。边界情况与常见误区空数组若任一输入为空建表或查表循环不执行最终返回[]算法天然正确无需特判。JS 实现中为什么存visited[num] num而不是visited[num] true这属于防御性写法JS 中对象键被存储为字符串但visited[0]访问时会自动完成类型转换因此数字0也能正确命中。若存布尔值需注意不要用if (visited[num])这类真值判断——当num对应的键不存在但visited[num]恰好为undefined时无碍但任何真值性判断而非! undefined都可能误伤边界值。原文档统一使用visited[num] num存元素本身、用visited[num] undefined清空配合! undefined判断逻辑最为稳妥。为什么 Python 用pop而不是重新赋值if num in visited判断的是键是否存在Python 版用visited.pop(num)直接删除键语义上比置空更彻底也避免键残留。思路拓展从本题延伸到同类问题本题是哈希表去重交集的入门题掌握后可以继续向两个方向延伸保留重复元素的进阶版本若题目改为输出结果中每个元素出现的次数应与该元素在两个数组中出现的次数一致即 Intersection of Two Arrays II 的设定则无法用命中即删的简单标记需要改为计数思路——建表时记录nums1中每个元素的出现次数查表命中后计数减一减到零才删除从而保留重复元素。这一思路与仓库中 [problems/350] 同类题目相比核心差异仅在于键的取值是布尔标记还是计数器。排序 双指针若数组本身有序参见仓库 problems/167.two-sum-ii-input-array-is-sorted.md 的双指针范式可先对两数组排序再用双指针同步推进元素相等则记录并同时前进、较小者单独前进达到 O(N log N) 时间、O(1) 额外空间的解法。这是空间换时间的另一面——用排序的时间代价换掉哈希表的空间。仓库索引与配套资源本题英文题解原文problems/349.intersection-of-two-arrays.en.md本题中文题解原文problems/349.intersection-of-two-arrays.md简单难度题目合集含本题定位collections/easy.md仓库主 README 简单题单README.md空间换时间算法思想论述thinkings/README.md【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考