两个数组的交集 II：哈希表、排序双指针与内存优化全解析

刷题刷到“两个数组的交集 II”这道题时我第一反应是这不就是求两个集合的交集吗但把题目读完发现没那么简单——它要求“每个元素出现次数与它在两个数组中出现的次数一致”也就是说重复元素要按次数保留。这个看起来只是多了个“II”的题目其实把哈希表、双指针、排序、二分查找这几个基础知识点全串起来了。我见过不少人在面试里碰到这道题第一版代码写出来能跑但一问“为什么选短的数组建哈希表”“如果内存放不下怎么办”就开始支支吾吾。这篇文章把我做题、讲题过程中积累的理解、代码、坑和延伸思路一次说清希望能给你省下一些走弯路的时间。1. 题目本身到底在考什么1.1 表面是求交集实际在考重复计数题目给定两个数组比如nums1 [1,2,2,1]、nums2 [2,2]返回交集是[2,2]。注意不是返回[2]因为数字2在两个数组里都出现了两次所以结果里也要出现两次。这一点就是和“两个数组的交集 I”最大的区别——那道题要求去重返回[1,2]或[2]就行这道题要求保留出现的最小次数。换句话说如果某个数在第一个数组出现 3 次在第二个数组出现 2 次交集中只能保留 2 次。怎么理解这个“最小次数”你可以想象两个袋子一个袋子里有 3 个红球另一个袋子里有 2 个红球。你把两个袋子倒在一起能从里面拿出来的红球最多就是 2 个因为第二个袋子只有 2 个。这就是min(count1, count2)的逻辑。1.2 为什么这道题值得单独拿出来写从刷题的角度这道题的难度标注是“简单”但它覆盖了算法面试里几个高频考点哈希表如何设计 key-valuevalue 存什么双指针法的适用前提数组有序海量数据场景下的内存优化思路输出结果的顺序有没有要求题目说可以不考虑顺序。我面试别人的时候也喜欢拿这道题做热身。它不像动态规划那么劝退又能快速看出一个人是背过答案还是真理解思路。很多候选人能写出哈希表解法但让他不用额外空间再写一遍就卡住了。所以这篇文章会把两种主流解法都讲透再把进阶问法也展开聊聊。2. 哈希表解法最简单也最容易出错的地方2.1 核心思路先数数再匹配哈希表解法是我推荐优先掌握的因为代码直观、时间复杂度是线性的。思路分两步遍历第一个数组用一个哈希表记录每个数字出现的次数遍历第二个数组每遇到一个数字就去哈希表里查。如果查到了且次数大于 0就把这个数字放进结果同时把哈希表里对应的次数减 1。整个过程就像你在柜台核销优惠券先把手里有的券张数记下来客人每拿一张券过来你就核对一下核销掉一张。2.2 参考代码Pythondef intersect(nums1, nums2): # 选择较短的数组建哈希表节省空间 if len(nums1) len(nums2): nums1, nums2 nums2, nums1 count {} for num in nums1: count[num] count.get(num, 0) 1 res [] for num in nums2: if count.get(num, 0) 0: res.append(num) count[num] - 1 return res这里有个细节我特别说一下为什么先交换数组让短的作为建表对象因为哈希表占用的空间取决于建表数组的长度。如果我们用较短的数组建表那额外空间就是O(min(m, n))。别小看这个优化在题目明确写“如果nums1比nums2小很多哪种算法更优”这种进阶问题时这就是关键得分点。还有一个容易忽略的点count.get(num, 0)的用法。很多新手会先写if num in count再取count[num]当然也可以但用get能让代码更简洁也避免 KeyError。2.3 时间复杂度与边界情况分析时间复杂度是O(m n)空间复杂度是O(min(m, n))。遍历两个数组各一次哈希表的增删查操作在平均情况下是O(1)所以整体是线性的。边界情况我在测试时都会主动覆盖两个数组都为空返回空数组一个为空一个不为空返回空数组数组里有负数哈希表对负数照样能正常处理因为 key 不要求非负两个数组完全没有交集返回空数组一个数字在一个数组中出现了很多次另一个数组只出现一次只保留一次。3. 排序双指针解法不用额外空间的做法3.1 为什么排序之后问题变简单了如果两个数组都是有序的我们可以用两个指针分别指向两个数组的头部然后比较指针所指的元素相等把这个元素加入结果两个指针同时后移左边小于右边左边指针后移左边大于右边右边指针后移。这个逻辑像什么就像两个人各自拿一叠按大小排好的卡片谁手里的卡片数字小谁就往后翻直到两张卡片相等就把这张卡片收起来。整个过程不依赖额外空间只要数组本身能排序。3.2 参考代码Pythondef intersect(nums1, nums2): nums1.sort() nums2.sort() i, j 0, 0 res [] while i len(nums1) and j len(nums2): if nums1[i] nums2[j]: i 1 elif nums1[i] nums2[j]: j 1 else: res.append(nums1[i]) i 1 j 1 return res写这段代码时有三处最容易出错指针移动条件写反。很多人一紧张就把“小于/大于”的移动方向搞反结果死循环。相等时忘记同时移动两个指针。如果只移动一个要么死循环要么会重复计数。nums1.sort()会改变原数组。如果题目要求不能修改原数组需要先拷贝一份再排序。3.3 复杂度对比与适用场景排序双指针的时间复杂度是O(m log m n log n)因为排序是主要开销。空间复杂度在 Python 的sort()是原地排序额外空间是O(1)如果语言内置排序不是原地版则要考虑O(m)或O(n)的额外空间。什么时候用哈希表什么时候用双指针我总结了一个简单的判断标准场景推荐方案理由两个数组都比较小哈希表时间复杂度低代码简单其中一个数组特别大哈希表建小数组节省空间不允许用额外空间排序双指针只需 O(1) 额外空间输入已经有序双指针甚至连排序都省了数据量大到内存放不下外排归并思路见第 4 节4. 进阶问法当数据大得内存放不下怎么办4.1 经典追问之一如果数组已经排好序呢这是面试官很喜欢加的前提条件“如果给定的数组已经排好序你会怎么优化”答案很简单直接用双指针连排序都省了时间复杂度降到O(m n)空间复杂度O(1)。递进问法到这里基本就能让人满意了。4.2 经典追问之二如果内存不足以一次性加载两个数组呢这种场景在实际工程里非常常见。比如两个文件每个都有几千万行整数机器内存只有几个 GB直接建哈希表很可能内存溢出。一个可行的解法是外部排序 归并把两个大文件分别切成多个小块每块能加载进内存对每个小块排序写回磁盘然后用多路归并的方式同时读取两个文件的有序数据块用双指针思路逐个比对。这种做法的核心是不让所有数据同时在内存里只保留当前比较需要的部分。我早年做日志分析时处理过类似需求当时用 Python 写了个简化版代码逻辑就是模拟“边读边比”的归并流程。4.3 进阶追问之三两个数组都很大但单个数字的取值范围很小如果数字的取值范围是0~1000思路就完全不一样了。我们可以不用哈希表而是直接用数组当计数桶遍历第一个数组时counts[num]遍历第二个数组时检查counts[num]是否大于 0。这种题看起来很小儿科但它考的是“数据结构选型取决于数据特征”的意识。面试官真正想看的是你会不会根据数据的实际分布调整方案而不是只会背哈希表模板。5. 实操中容易踩的坑5.1 用哪个数组建哈希表无所谓不有所谓如果不假思索地固定用nums1建表而nums1又特别大空间开销就上去了。虽然题目没有强制要求最优空间但习惯好的做法是先比较长度用短的建表。这个习惯以后在真实工程里也很有用比如两个订单表 JOIN优化器一定会选小表驱动大表思路一模一样。5.2 遍历第二个数组时忘记减次数我见过不少代码遍历第二个数组时只判断if num in count然后把数字加进结果却没有把计数减一。这样会导致什么问题看这个例子nums1 [1,1,1]nums2 [1]正确结果是[1]。如果不减计数结果会变成[1,1,1]因为只要nums1里有1每次遇到1都会通过判断。记住一个原则每次匹配成功哈希表里的计数必须递减表示这个“库存”已经用掉了一次。5.3 双指针解法里的死循环风险双指针的边界条件非常细。常见错误是把nums1[i] nums2[j]写成nums1[i] nums2[j]相等时本应同时移动两个指针现在只移动了一个另一个指针停在原地下一次比较还是相等又只移动一个……循环往复等于在相等分支里绕圈甚至可能越界。我调试过一段类似的代码最后是打印每一步的i、j和数组内容才发现问题。现在我的习惯是写双指针之前先在注释里把三个分支的移动规则写清楚再动键盘。5.4 返回值格式和顺序要求题目说“可以不考虑输出结果的顺序”所以[2,2]和[2,2]只有一种排法不存在问题但如果是[1,2]和[2,1]两种都算对。不过有些面试官会追加要求“按第一个数组中的顺序输出”那就需要在哈希表解法里保留“遍历第二个数组”的顺序或者把结果再按某个规则排序。写之前先确认需求别默认题目说什么就是什么。6. 从题目到工程场景的延伸思考6.1 电商里求两个用户的共同购买商品假如你有一份用户购买记录每个商品对应一个 ID想知道两个用户都买过什么买了几次——这就是“两个数组的交集 II”的翻版。差别在于真实数据里用户 ID 和商品 ID 可能是字符串数组长度可能是百万级。哈希表方案完全可以支持只要单个用户购买列表能放进内存。我在模拟项目X里做过类似的功能用于给用户打标签。当时一个用户的购买记录平均几千条两个用户求交集用Counter做与运算几毫秒就出结果。6.2 日志分析里求两个时段都出现的错误码运维场景中有两个时间窗口的报错日志每个窗口里有一堆错误码想知道两个窗口都出现了哪些错误码以及出现次数。思路完全一样。唯一要注意的是错误码可能带参数直接拿完整字符串做 key 会导致不同参数算成不同错误码所以一般要先做一层归一化只提取错误码主体部分。6.3 相似度计算的基石在推荐系统、文本去重里经常要算两个集合的 Jaccard 相似度公式是交集大小除以并集大小。求交集大小这一步本质就是在算两个数组的交集。如果数据量特别大还可以用布隆过滤器先粗筛一遍把明显不可能出现在交集里的元素过滤掉减少精确计算的数据量。这类题目表面简单但它在工程里的变体无处不在。把基础解法吃透再理解它在真实场景里的变形方式刷一道题远远比重复刷十道简单题的价值大。我在实际做题和讲题过程中最大的体会是这道题最值得记住的不是某一版代码而是“同一个问题在不同约束下要切换不同解法”的意识。哈希表空间够但费内存排序双指针省内存但多花时间如果输入有序就什么都不用做——算法面试考的不是你会不会背而是你会不会选。下次碰到两数组、两文件、两集合求共同元素的需求可以先停下来想一想数据长什么样内存够不够是否有序这三个问题想清楚了方案自然就浮出来了。