两个数组的交集（LeetCode 0349）：哈希表与分离双指针解法详解 —— 出自「算法通关手册」AlgoNote

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文以 0349. 两个数组的交集 题解文档为核心结合「算法通关手册」AlgoNote 仓库中的哈希表、双指针专题文档深入讲解求两个数组交集去重的两种经典解法。读完本文你将掌握「哈希表计数去重」与「排序 分离双指针」两类高频技巧的推导过程、完整可运行代码、复杂度分析以及它们与 0350. 两个数组的交集 II 的进阶差异能够举一反三地应对面试中的数组交集类问题。1. 题目大意描述给定两个数组nums1和nums2返回两个数组的交集重复元素只计算一次。说明1 nums1.length, nums2.length 10000 nums1[i], nums2[i] 1000示例示例 1输入nums1 [1,2,2,1], nums2 [2,2] 输出[2]示例 2输入nums1 [4,9,5], nums2 [9,4,9,8,4] 输出[9,4] 解释[4,9] 也是可通过的从示例可以看出本题有两个核心考察点一是交集的定义——元素必须同时出现在两个数组中二是去重——nums1中的重复元素2、nums2中的重复元素9/4在最终答案中都只能出现一次。这也是本题与 0350. 两个数组的交集 II要求保留与出现次数一致的多重元素最本质的区别。从仓库的题目归类看本题被标注为「数组、哈希表、双指针、二分查找、排序」标签难度为简单见 00_06_categories_list.md 题目列表。这意味着它至少有哈希表、双指针、排序、二分查找四条可解路径本文重点讲解仓库题解中给出的两条主线哈希表与分离双指针。2. 思路 1哈希表2.1 解题思路哈希表的解法分两步先遍历第一个数组nums1利用哈希表Python 中即字典dict存放nums1中出现过的元素对应字典值设为1。再遍历第二个数组nums2如果哈希表中存在该元素则将该元素加入答案数组并将该键对应的值减一清空该键的可用性从而保证同一个元素最多被记录一次。这里的关键设计是用字典值是否为 0来充当该元素是否已被取走的标记。当nums2中再次出现同一个元素时由于值已经变为0numDict[num] ! 0的条件不成立就不会重复加入答案天然实现了去重。这一思路背后正是哈希表以空间换时间的核心思想通过哈希函数把关键字key映射到存储位置实现近似 $O(1)$ 的插入与查找。关于哈希函数设计直接定址法、除留余数法、平方取中法、基数转换法等与哈希冲突解决策略开放地址法、链地址法的完整理论可阅读仓库专题文档 哈希表。2.2 参考代码class Solution: def intersection(self, nums1: List[int], nums2: List[int]) - List[int]: numDict dict() nums [] for num in nums1: if num not in numDict: numDict[num] 1 for num in nums2: if num in numDict and numDict[num] ! 0: numDict[num] - 1 nums.append(num) return nums代码要点第一重循环只做存在性登记把nums1中出现过的元素作为字典的键第二重循环用numDict[num] ! 0判断该元素是否已经被取走取走后值减一实现去重返回值顺序不敏感示例 2 中[4, 9]也被判为正确。2.3 复杂度分析时间复杂度$O(n)$。两轮线性遍历哈希表的插入与查找平均为 $O(1)$。空间复杂度$O(n)$。主要消耗在存放nums1元素的哈希表上。从哈希表专题文档可知Python 字典底层的哈希冲突处理是链地址法当关键字分布均匀时单个槽位链表长度 $k \approx n/m$查找复杂度接近 $O(1)$这正是本解法能在 $O(n)$ 时间内完成的原因。3. 思路 2分离双指针3.1 解题思路分离双指针是仓库 双指针专题文档 中定义的三大双指针范式之一分别在两个不同数组上各设置一个指针两个指针独立地在各自数组中移动以协同完成任务。其前提条件是两个数组均已有序因此需要先排序对数组nums1、nums2分别排序。使用两个指针left_1、left_2均初始化为0分别指向两个数组的起始位置。如果nums1[left_1] nums2[left_2]则将nums1[left_1]加入答案数组注意去重并将left_1和left_2同时右移。如果nums1[left_1] nums2[left_2]说明nums1当前元素不可能出现在交集里nums2中后续元素只会更大将left_1右移。如果nums1[left_1] nums2[left_2]同理将left_2右移。当任一指针越界时结束循环返回答案数组。指针移动的单调性保证了算法不会漏掉任何交集元素每次比较都排除掉更小一侧的当前元素剩下的比较范围严格收窄整个过程只需要线性扫描一遍。3.2 参考代码class Solution: def intersection(self, nums1: List[int], nums2: List[int]) - List[int]: nums1.sort() nums2.sort() left_1 0 left_2 0 res [] while left_1 len(nums1) and left_2 len(nums2): if nums1[left_1] nums2[left_2]: if nums1[left_1] not in res: res.append(nums1[left_1]) left_1 1 left_2 1 elif nums1[left_1] nums2[left_2]: left_1 1 elif nums1[left_1] nums2[left_2]: left_2 1 return res3.3 去重优化利用有序性上述代码在相等分支里用nums1[left_1] not in res判断去重这是 $O(k)$ 的线性查找k为当前结果长度。由于数组已经有序相等分支连续命中的元素必然相同因此可以借助 双指针专题文档 中的优化写法把去重判断降为 $O(1)$if not res or nums1[left_1] ! res[-1]: res.append(nums1[left_1])只需与结果数组的最后一个元素比较即可因为有序数组保证下一个待加入的交集元素要么与上一个相同需去重要么更大直接加入。该优化不会改变算法的时间复杂度量级但常数更小。3.4 复杂度分析时间复杂度$O(m \log m n \log n)$其中 $m$ 和 $n$ 分别为两个数组的长度。排序用时 $O(m \log m n \log n)$双指针遍历用时 $O(m n)$因此总时间复杂度为 $O(m \log m n \log n)$。空间复杂度$O(\min(m, n))$。主要消耗在答案数组上最多不超过较短数组的去重元素个数。需要说明的是Python 的list.sort()为原地排序Timsort不额外占用结果集以外的显著空间若采用非原地排序实现则需计入排序辅助空间。4. 两种思路对比与选型维度思路 1哈希表思路 2分离双指针是否要求有序不要求要求需先排序时间复杂度$O(n)$$O(m \log m n \log n)$空间复杂度$O(n)$哈希表$O(\min(m, n))$答案数组去重手段字典计数归零有序性判断 /not in检查适用场景不修改原数组、只读遍历允许排序、追求常数空间、结果需要有序选型建议若不允许修改原数组或希望保持原始数据优先用哈希表思路 1它只读遍历、实现最简洁若允许排序且希望控制额外空间可选用双指针思路 2排序后还能顺带得到有序的输出结果当两个数组规模差异悬殊如 $m \ll n$时可考虑对短数组哈希登记 遍历长数组查询或排序长数组 对短数组逐个二分查找的思路——本题标签中的「二分查找」「排序」正对应这一类变体。注意仓库题解文档以哈希表与双指针为主二分变体属于标签隐含的可拓展方向面试中可作为加分项自行推导。5. 进阶与 0350「两个数组的交集 II」的区别本题的直接进阶题是 0350. 两个数组的交集 II两者题目描述几乎一致但输出规则不同0349重复元素只计算一次输出集合意义下的交集0350每个元素出现的次数与两个数组中出现的次数一致不一致时取较小值输出多重集合意义下的交集。对应的哈希表解法差异也体现在计数语义上0349 的字典值只取1和0两个状态充当是否已取走的标记0350 的字典记录每个元素的真实出现次数遍历nums2时每取走一次就numDict[num] - 1直到计数为0才不再输出从而保留多重元素。对比两条题解可以更直观地理解集合去重与多重集合计数两种数据建模方式的差别建议将两题放在一起刷作为同一考点的正反对照。6. 在仓库中的延伸学习路径本题在「算法通关手册」AlgoNote 仓库中不是孤立一题而是串联多个专题的核心例题哈希表专题哈希表 文档系统讲解了哈希函数设计与冲突解决本题是其练习题目一节的指定练习同组练习题还包括 0217. 存在重复元素、0219. 存在重复元素 II、0036. 有效的数独 等。双指针专题双指针 文档将本题列为「分离双指针」的经典例题给出了分离双指针的通用解题模板初始化两指针指向数组头部 → 相等则同时右移 → 较小侧单边右移 → 指针越界结束。该模板可以直接迁移到有序数组合并、并集等同类问题。题目总览在 00_06_categories_list.md 分类列表 中可查看到本题的标签、难度与题解入口便于按标签批量刷题。7. 总结「两个数组的交集」虽然标记为简单题却同时覆盖了哈希表、排序、双指针、二分查找四类高频考点是面试中的经典送分题与变式题母题哈希表法$O(n)$ 时间、$O(n)$ 空间用计数归零优雅地去重无需改动原数组分离双指针法$O(m \log m n \log n)$ 时间、$O(\min(m, n))$ 空间先排序后线性扫描输出天然有序并可通过res[-1]比较把去重优化为 $O(1)$掌握上述两种范式后再看 0350 进阶题 以及两个有序数组求交集的面试变体都能在几分钟内给出最优解。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0169 多数元素——哈希表与分治双解法精讲AlgoNote 算法通关手册LeetCode 0169 多数元素——哈希表与分治双解法精讲 本篇题解来自 AlgoNote「算法通关手册」题解体系围绕 L教程文档知识库3大突破性功能AMD Ryzen处理器深度调试完全指南3大突破性功能AMD Ryzen处理器深度调试完全指南 想要彻底释放你的AMD Ryzen处理器性能潜力吗SMUDebugTool这款终极硬件调试神器为你提教程文档知识库AlgoNote 算法通关手册LeetCode 137「只出现一次的数字 II」哈希表与位运算双解法精讲AlgoNote 算法通关手册LeetCode 137「只出现一次的数字 II」哈希表与位运算双解法精讲 本篇题解围绕「算法通关手册」AlgoNote中的教程文档知识库上一篇Agent OS 与 OWASP Agentic Top 10原生 ACS 策略与宿主安全控制的治理映射实战下一篇IntelliJ Swing 组件架构实战在 intellij-community 中用单向数据流构建特性组件创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考