刷力扣350之前我建议你先想清楚“交集”到底交的是什么刷到力扣350这道题很多人第一反应是“这不就是两个数组求交集嘛”等看清题目要求才发现坑藏在“出现次数”四个字里。它跟349的区别就像“查两个人的共同好友”和“查两个人有哪些共同好友、并且每个人同时都认识了几个”的区别前者只看名单后者还要数人头。这题在面试里的出现频率不低常见考法不只是让你写出来还会连环追问数组有序怎么办、一个大一个小怎么办、一个数组大到没法进内存怎么办。把这些答透比单纯AC一道题值钱得多。适合谁来刷刚接触哈希表或双指针的初学者可以把这题当成入门练手准备面试的人更要把后面的进阶问法当重点。题目本身不难但能在二十分钟内把“基础解法进阶优化边界讨论”讲清楚就是一轮很稳的算法面。1. 题意拆解为什么叫“交集2”不叫“交集”1.1 先搞清楚题目到底要返回什么力扣350的题目描述很短给定两个数组编写一个函数来计算它们的交集。示例一看就明白了nums1 [1, 2, 2, 1]nums2 [2, 2]返回 [2, 2]nums1 [4, 9, 5]nums2 [9, 4, 9, 8, 4]返回 [4, 9] 或 [9, 4] 都行注意“出现次数”这个措辞。nums1 里的 2 出现了两次nums2 里的 2 也出现了两次所以结果里出现两次。如果 nums1 [2, 2, 2]nums2 [2, 2]结果应该是 [2, 2]取两个数组里 2 的次数的较小值也就是 min(3, 2) 2。这里很容易忽略一点返回结果的顺序任意。有人会额外排序试图对照样例输出其实完全没必要只要元素和次数对LeetCode 是接受任意顺序的。顺序无所谓这个灵活性在多解法设计时很重要尤其是哈希表那套方案天然就是无序的。1.2 和349的差别一个去重一个计数力扣349“两个数组的交集”只要求返回唯一的交集元素比如 nums1 [1, 2, 2, 1]nums2 [2, 2]349 返回 [2]350 返回 [2, 2]。区别的本质在于349面对的是“集合”集合天然没有重复350面对的是“多重集合”也就是每个元素还带了一个出现次数。用生活类比来理解349问的是“哪些餐厅两个人都去过”350问的是“哪些餐厅两个人分别去了几次取两人都去过的次数最小值”。前者用 HashSet 就能解决后者必须用 HashMap 或者有序数组去统计次数。这个差距引导出两类思路哈希计数维护一个“库存表”排序后用双指针同时扫描两个有序数组。两条路线都值得写一遍因为面试官很可能会让你从一条换到另一条看你知不知道各自的时间、空间代价。1.3 整盘解题路线图我给自己定的解题顺序是这样的第一步确定理解“次数取较小值”写一个简单例子验证下第二步推荐先写哈希表方案代码短、不容易错复杂度清晰第三步主动补上排序加双指针方案并说明空间优势第四步准备回答进阶追问如果已经排好序、如果长度悬殊、如果数组太大无法载入内存。前三步是做题第四步是面试里的加分项。下面我按这个顺序展开。2. 哈希表解法把出现次数当库存来扣2.1 核心思路给每个元素建一张“库存表”哈希表方案的思路很直接遍历第一个数组统计每个元素出现的次数得到一个计数器再遍历第二个数组每遇到一个元素就去计数器里查有没有“库存”有库存就把它加入答案同时把库存减一没有库存就跳过。为什么要减一而不是查到存在就追加因为要守住“次数取最小值”的规则。我见过不少初学者写成“nums2 里的元素在 nums1 出现过就加进结果”这样写出来的答案会把重复次数放大。举一个极端例子nums1 [1]nums2 [1, 1, 1, 1]如果只判断“出现过”结果会是 [1, 1, 1, 1]但交集最多只能有一个 1。正确结果应该是 [1]。把计数器想象成“库存台账”第一个数组告诉你有多少存货第二个数组每领走一件就登记一笔库存变成 0 之后再来人也不能领了。这样天然就落实了 min 规则。哈希表的另一个好处是支持非排序数组。题目不保证两个数组有序这意味着我们可以在 O(m n) 的时间内完成而排序解法至少是 O(mlogm nlogn)。如果数组本身数据量中等哈希法的速度优势非常明显。2.2 代码实现Python 和 Java 两个版本先用 Python 写一份最经典的from collections import Counter def intersect(nums1, nums2): # 为了省空间选较短的数组建表 if len(nums1) len(nums2): nums1, nums2 nums2, nums1 cnt Counter(nums1) result [] for x in nums2: if cnt.get(x, 0) 0: result.append(x) cnt[x] - 1 return result这里有两个细节值得说。第一为什么先把短数组换到 nums1因为计数器大小只取决于被统计的数组长度。我们始终拿短数组建表遍历长数组寻找匹配哈希表内存占用就是 O(min(m, n))而不是 O(m) 或 O(n) 里更差的那个。第二cnt.get(x, 0)是必须的。直接写if cnt[x] 0时如果 x 没在计数器里Python 会抛 KeyError报错报得莫名其妙排查时还容易忽略。如果想更贴近 Java 面试手写也可以看一下这个版本class Solution { public int[] intersect(int[] nums1, int[] nums2) { if (nums1.length nums2.length) { return intersect(nums2, nums1); } MapInteger, Integer counts new HashMap(); for (int n : nums1) { counts.put(n, counts.getOrDefault(n, 0) 1); } ListInteger list new ArrayList(); for (int n : nums2) { int c counts.getOrDefault(n, 0); if (c 0) { list.add(n); counts.put(n, c - 1); } } int[] res new int[list.size()]; for (int i 0; i res.length; i) { res[i] list.get(i); } return res; } }Java 版本的思路一模一样只是把 Python 的 Counter 换成 HashMap。注意 Java 里list.stream().mapToInt(...).toArray()也能达到同样效果但面试手写时我会避免用流因为部分面试官希望看到基础循环写法并且流式代码在小数据量时看不出问题性能敏感场景下反而容易成为争论点。2.3 复杂度分析时间 O(m n)空间 O(min(m, n))设定 m len(nums1)n len(nums2)。建计数器遍历短数组 O(min(m, n))扫描长数组遍历长数组 O(max(m, n))总体时间复杂度 O(m n)空间复杂度主要来自哈希表是 O(min(m, n))输出数组不计入额外空间。这组数字背下来用处很大。面试官问“为什么不用排序解法”你可以直接说当两个数组都无序时哈希法把时间控制在线性级别代价是多用了哈希表的空间。如果题目对空间有限制或者要求原地完成那就换排序双指针。2.4 易错点补充递减到零以后别忘判断我在试跑这类代码时踩过一个典型坑写了if x in cnt:而不是if cnt[x] 0:。前者只能保证元素存在不能保证库存还有。如果 nums1 里 2 只有一次nums2 里 2 有三次用x in cnt会输出三个 2答案错误。另一个隐蔽问题是有人会在循环里删除键if cnt.get(x, 0) 0: result.append(x) cnt[x] - 1这样没问题因为减到 0 后get返回 0不会再进入分支。没有必要写成if cnt[x] 1: del cnt[x]之类删除键反而增加操作还可能让get返回默认值的同时让人误以为元素彻底消失日志调起来多一层困惑。减到零和删除键在语义上有细微差别但在这个题目里减到零就够用了。3. 排序加双指针空间换时间里的另一个极端3.1 思路拆解把无序变成有序扫描一次拿下哈希表方案很快但面试官追问“你能不用额外哈希表吗”时就要亮出排序加双指针。思路分两步分别给两个数组排序用两个指针 i 和 j 分别指向 nums1 和 nums2 的开头比较当前元素。比较时有三种情况nums1[i] nums2[j]说明 nums1 当前元素太小不可能在 nums2 里找到匹配i 前进nums1[i] nums2[j]说明 nums2 当前元素太小j 前进nums1[i] nums2[j]记录这个值i 和 j 同时前进。这个过程的本质是同时扫描两个有序数组谁小谁动相等则同时动自然控制了“次数取较小值”。举例来说nums1 [1, 2, 2, 2]排序后还是这个nums2 [2, 2, 3]排序后还是这个。i 走到第二个 2 时j 已经超过第二个 2后面不会再匹配这就保证了结果最多只有两个 2而不是三个。排序后的数组让重复元素紧凑排列双指针的“谁小谁动”天然是对的。如果数组是无序的这个策略完全失效因为小元素可能出现在后面你无法判断“当前元素太小”是否永远成立。3.2 代码实现核心循环只有几行def intersect(nums1, nums2): nums1.sort() nums2.sort() i, j 0, 0 result [] while i len(nums1) and j len(nums2): if nums1[i] nums2[j]: i 1 elif nums1[i] nums2[j]: j 1 else: result.append(nums1[i]) i 1 j 1 return result这个实现的简洁程度不输哈希表但边界条件更值得小心。while i len(nums1) and j len(nums2)两个条件缺一不可。我见过有人写成while i len(nums1)然后在内部判断if j len(nums2): break虽然也能跑但读起来绕写起来更容易漏。直接维护双条件最稳。排序用原地 sort不复制新数组。Python 的 Timsort 在数组包含大量相同元素时表现很好Java 对 int[] 排序用的是双枢轴快速排序平均 O(nlogn)。算法题场景下直接用语言内置排序就够了手写排序属于自找麻烦还容易出错。3.3 复杂度分析排序是主要成本双指针本身很便宜时间复杂度排序耗时 O(mlogm nlogn)双指针扫描耗时 O(m n)总时间复杂度 O(mlogm nlogn)空间复杂度如果不把排序递归栈算进去双指针只用了 i、j 和 result额外空间接近 O(1)。严格按通用理论快排和 Timsort 都有栈开销通常记为 O(mlogm nlogn) 的排序空间或 O(mn) 的临时空间但很多面试官会接受“额外空间基本 O(1)”的说法因为排序可以在原数组上进行。这个方案适合什么时候用两个数组无序但是对空间敏感或者你能接受耗时换来更低的额外内存。真实面试里两个方案都要能写单纯背一个会显得解题思路不完整。4. 面试进阶三连问这题真正的加分项4.1 数组已经排好序怎么优化这是力扣给出的第一个进阶问题。如果两个数组都已经有序那么哈希表方案就有点“杀鸡用牛刀”了直接双指针 O(m n) 搞定空间 O(1)。排序方案中的“排序”可以直接省掉剩下来的扫描本身就是最优的。如果只有一个数组有序另一个无序那情况要分两种数组长度接近排序无序的那个再用双指针复杂度 O(klogk k)k 是较长的数组长度短数组 vs 长有序数组可以给无序的短数组排序或者逐元素在有序长数组里做二分查找。对短数组的每个元素做二分查找是 O(mlogn)m 小的时候比 O(m n) 更划算。我在面试现场回答这类追问时的顺序是先确认数组是否有序再根据长度关系选择“双指针”还是“短表哈希”或“二分”。不要一上来就报最优解先把前置条件讲清楚这在系统设计类问题里也是同样的表达习惯。4.2 两个数组长度相差悬殊选哪个力扣的第二个进阶问题是如果 nums1 比 nums2 小很多哪种方法更好结论是哈希表法更好但要写成“拿短数组建表”。因为短数组的 HashMap 大小是 O(min(m, n))遍历长数组一次就能把所有交集找出来整体时间 O(m n)。排序加双指针则必须把两个数组都排一遍排序成本是 O(mlogm nlogn)n 很大时非常浪费计算。实际操作时可以先交换两个数组让短数组在前再套用之前的哈希代码。这就是我在 2.2 里先写交换逻辑的原因它不只是一个优化技巧还正好回答了这个进阶问题。如果你非要追求极致可以试试对短数组排序然后遍历长数组时用二分查找或双指针定位窗口。这种做法适合长数组本身有序的场景时间复杂度能压到 O(mlogm nlogm)但代码复杂度比纯哈希高性价比一般。面试中能说出“长度悬殊时哈希表更优”这个结论就够了。4.3 内存受限大数组在磁盘上怎么办这题还有一个非常经典的进阶场景nums2 存储在磁盘上内存装不下。很多人被问到这里就卡住其实考察的是对“内存模型”和“外部排序”的理解。先说一个前提如果小数组能整个进内存那么直接把小数组做成哈希表然后分批读大数组。伪代码如下# 伪代码不代表可直接运行 cnt Counter(小数组) with open(big_array.txt) as f: for line in f: for x in line.split(): if cnt.get(x, 0) 0: result.append(x) cnt[x] - 1这种方案的好处是大数组以流的形式被读取永远不需要一次载入。哈希表占用的内存只跟小数组有关。如果两个数组都大到无法进内存就必须走“外部排序 归并”的路线。流程大致如下把大数组切成多个块每块能读进内存对每块在内存里排序再写回磁盘形成若干个有序小文件使用多路归并把所有有序小文件合并得到全局有序的大数组这个合并过程可以边排序边输出拿到两个全局有序的文件后用两个指针做归并扫描谁小谁前进相等记录并同时前进。外部排序的关键不是“排序算法本身多快”而是“磁盘 IO 次数尽量少”。每轮归并尽可能多地合并已排序块减少磁盘读写轮数。面试中说出分块排序、写回、归并这几步就足以体现对内存受限场景的理解。更深的细节面试官会让你估算 IO 数量那就涉及“多路归并的读放大”不过这道题通常不会追问到那么深。还有一条思路是把交集问题转换成数据库 JOIN对两个数组去重计数再按照共同键做聚合。实际工程里这个方案很常见但算法面试里聊这个容易跑偏回答时分寸要把握好提到外部归并就够了。5. 常见问题与调试实录5.1 哈希表方案翻车实录我在这道题上看到的高频提交错误第一个就是忘记“库存减一”。尤其当 nums2 里某个重复元素特别多时结果会直接溢出正确次数。这种错误在样例nums1 [1,2,2,1]、nums2 [2,2]上不一定暴露因为两边重复次数刚好都是 2一旦改成nums1 [1,1,2]、nums2 [1,1,1,1]就立刻出错。所以写完一定要自己造这种极端用例。第二个高频错误是 KeyError。Python 代码里直接写if cnt[x] 0而 x 不在表里会抛异常。使用get(x, 0)是标准做法也是把“查表”和“查默认值”合成一次操作。记住cnt[x] - 1在 x 存在时是安全的但一旦键被提前删除就会 KeyError所以尽量别在循环里删键。第三个错误是边界情况没处理好。比如nums1 []此时计数器为空扫描 nums2 一个都不匹配结果为空其实代码能正确处理但如果你为了优化手写了交换逻辑要确认交换后的空数组不会导致索引操作。我写的版本里交换逻辑本身不会造成这个问题因为后续只对非空数组的 Counter 查询。5.2 双指针方案翻车实录双指针最常见的 bug 是内层条件写错。我早期写过这样的代码while i len(nums1) and j len(nums2): if nums1[i] nums2[j]: i 1 if nums1[i] nums2[j]: # 错误i可能已经越界 j 1当 nums1[i] nums2[j] 执行 i 1 后下一行还在同一个 if 结构里用 nums1[i]如果 i 已经变成 len(nums1)立刻越界。这个错误非常隐蔽因为有些测试样例恰好不会触发越界只有走到数组末尾才崩。修复方式很简单把第二个 if 改成 elif保证只有第一个条件不成立时才执行第二轮判断。还有一个我个人很推荐的调试顺序先打印 i、j、nums1[i]、nums2[j]每轮循环看一眼。不要看完整结果看其中一轮就行。这样可以立刻发现指针是否跳过头或者进入了死循环。用纸笔模拟三个用例一方为空、一方更短、双方长度一致但重复元素分布不均衡基本能覆盖九成边界问题。5.3 边界用例速查表以下用例是我每次手写完这道题后默认会跑的它们能快速验证程序正确性强烈建议存在本地笔记里用例nums1nums2期望输出说明空数组[][1,2][]一方为空无交集[1,2,3][4,5][]完全没有共同点完全包含[1,2,3][3,2,1][1,2,3]顺序无所谓次数受限[2,2,2][2,2][2,2]取最小次数负数参与[-1,0,3][0,-1,-1][-1,0]哈希表不受负数影响大数重复[100000, 100000][100000][100000]数值大小不影响完全相同[7,7][7,7][7,7]完全相同时长度也相等到表里的最后一种情况容易被忽略一个数组完全等于另一个数组双指针方案里会出现两个指针同时走到底结果长度等于原数组长度程序正确返回所有元素这也能顺带验证 while 循环终止条件。6. 从这道题延伸出去一套解法套路覆盖一串题6.1 相似题型与变式力扣350不是孤立的题它和不少题目共享同一套思考方式349 两个数组的交集把 350 的“计数”变成“存在”用 HashSet 即可88 合并两个有序数组双指针从尾部开始填思路接近排序版双指针剑指Offer 03 数组中重复的数字哈希表计数找重复349 和350一起看能理解“集合”和“多重集合”的区别这个理解在很多设计题里都有用。难度升级后还会看到“两个数组的交集 III”之类的变体可能要求返回最长公共子序列那就要引入动态规划。但350本身只要求连续相等的公共部分不需要跳跃匹配所以双指针足够。想刷透这个知识模块我的建议是把349、350、88、以及“找出所有消失的数字”放在同一批练习。这几道题组合起来覆盖了哈希表、双指针、下标映射三个高频手段。6.2 工程里“数组交集”到底用在哪儿别觉得这题只会出现在面试里。实际业务里“求两个列表的共同元素”太常见了两个用户标签系统的标签重叠部分要算用户相似度会用到集合交集权限系统里判断某个角色是否有某个权限本质是把用户权限列表和资源要求列表做交集日志系统里同一时间段访问过 A 页面和 B 页面的用户ID直接对两个数组求交集就是最简单的漏斗分析推荐系统里把不同召回结果做去重合并本质上也是多集合的交并补。当数据量到达千万级以上就不能再用 Python 的set一把梭了。这时候要引入 Bloom Filter 之类的概率结构先粗筛再做内存映射或外部排序。350 的“进阶”部分恰好就是这些工程问题的简化版。我在公司内部做过一次“共同访问用户”的统计当时两个日志文件各有两千多万行。直接读进内存做哈希峰值内存冲到 3GB机器差点挂掉。后来改成外部排序分块归并内存稳定在 200MB 左右跑完。做完之后我再回头看350才真正理解力扣为什么把“大数组在磁盘上”写成一个进阶问题因为这是真实会撞上的问题。最后再分享一个我自己常用的复盘动作做完350我会额外做一件小事把“哈希法”和“排序双指针”的写题时间各自掐一遍表。哈希法我一般能进两分钟双指针加排序也能在三分钟内搞定。这个时间感觉没什么意义但面试时很管用——脑子里有两条路线就不会因为换一种问法就当场大脑空白。如果你第一次刷这题建议先别打开题解自己花十五分钟写哈希版再花十五分钟写双指针版然后对照本文的进阶问题自问自答一遍。这十五分钟换来的不只是一道题的AC而是一套“数组重叠问题”的完整解题框架。以后遇到再花哨的交集变体你也能一眼看出它是在考计数还是在考指针移动。
力扣350数组交集：哈希表与双指针的进阶面试全解
刷力扣350之前我建议你先想清楚“交集”到底交的是什么刷到力扣350这道题很多人第一反应是“这不就是两个数组求交集嘛”等看清题目要求才发现坑藏在“出现次数”四个字里。它跟349的区别就像“查两个人的共同好友”和“查两个人有哪些共同好友、并且每个人同时都认识了几个”的区别前者只看名单后者还要数人头。这题在面试里的出现频率不低常见考法不只是让你写出来还会连环追问数组有序怎么办、一个大一个小怎么办、一个数组大到没法进内存怎么办。把这些答透比单纯AC一道题值钱得多。适合谁来刷刚接触哈希表或双指针的初学者可以把这题当成入门练手准备面试的人更要把后面的进阶问法当重点。题目本身不难但能在二十分钟内把“基础解法进阶优化边界讨论”讲清楚就是一轮很稳的算法面。1. 题意拆解为什么叫“交集2”不叫“交集”1.1 先搞清楚题目到底要返回什么力扣350的题目描述很短给定两个数组编写一个函数来计算它们的交集。示例一看就明白了nums1 [1, 2, 2, 1]nums2 [2, 2]返回 [2, 2]nums1 [4, 9, 5]nums2 [9, 4, 9, 8, 4]返回 [4, 9] 或 [9, 4] 都行注意“出现次数”这个措辞。nums1 里的 2 出现了两次nums2 里的 2 也出现了两次所以结果里出现两次。如果 nums1 [2, 2, 2]nums2 [2, 2]结果应该是 [2, 2]取两个数组里 2 的次数的较小值也就是 min(3, 2) 2。这里很容易忽略一点返回结果的顺序任意。有人会额外排序试图对照样例输出其实完全没必要只要元素和次数对LeetCode 是接受任意顺序的。顺序无所谓这个灵活性在多解法设计时很重要尤其是哈希表那套方案天然就是无序的。1.2 和349的差别一个去重一个计数力扣349“两个数组的交集”只要求返回唯一的交集元素比如 nums1 [1, 2, 2, 1]nums2 [2, 2]349 返回 [2]350 返回 [2, 2]。区别的本质在于349面对的是“集合”集合天然没有重复350面对的是“多重集合”也就是每个元素还带了一个出现次数。用生活类比来理解349问的是“哪些餐厅两个人都去过”350问的是“哪些餐厅两个人分别去了几次取两人都去过的次数最小值”。前者用 HashSet 就能解决后者必须用 HashMap 或者有序数组去统计次数。这个差距引导出两类思路哈希计数维护一个“库存表”排序后用双指针同时扫描两个有序数组。两条路线都值得写一遍因为面试官很可能会让你从一条换到另一条看你知不知道各自的时间、空间代价。1.3 整盘解题路线图我给自己定的解题顺序是这样的第一步确定理解“次数取较小值”写一个简单例子验证下第二步推荐先写哈希表方案代码短、不容易错复杂度清晰第三步主动补上排序加双指针方案并说明空间优势第四步准备回答进阶追问如果已经排好序、如果长度悬殊、如果数组太大无法载入内存。前三步是做题第四步是面试里的加分项。下面我按这个顺序展开。2. 哈希表解法把出现次数当库存来扣2.1 核心思路给每个元素建一张“库存表”哈希表方案的思路很直接遍历第一个数组统计每个元素出现的次数得到一个计数器再遍历第二个数组每遇到一个元素就去计数器里查有没有“库存”有库存就把它加入答案同时把库存减一没有库存就跳过。为什么要减一而不是查到存在就追加因为要守住“次数取最小值”的规则。我见过不少初学者写成“nums2 里的元素在 nums1 出现过就加进结果”这样写出来的答案会把重复次数放大。举一个极端例子nums1 [1]nums2 [1, 1, 1, 1]如果只判断“出现过”结果会是 [1, 1, 1, 1]但交集最多只能有一个 1。正确结果应该是 [1]。把计数器想象成“库存台账”第一个数组告诉你有多少存货第二个数组每领走一件就登记一笔库存变成 0 之后再来人也不能领了。这样天然就落实了 min 规则。哈希表的另一个好处是支持非排序数组。题目不保证两个数组有序这意味着我们可以在 O(m n) 的时间内完成而排序解法至少是 O(mlogm nlogn)。如果数组本身数据量中等哈希法的速度优势非常明显。2.2 代码实现Python 和 Java 两个版本先用 Python 写一份最经典的from collections import Counter def intersect(nums1, nums2): # 为了省空间选较短的数组建表 if len(nums1) len(nums2): nums1, nums2 nums2, nums1 cnt Counter(nums1) result [] for x in nums2: if cnt.get(x, 0) 0: result.append(x) cnt[x] - 1 return result这里有两个细节值得说。第一为什么先把短数组换到 nums1因为计数器大小只取决于被统计的数组长度。我们始终拿短数组建表遍历长数组寻找匹配哈希表内存占用就是 O(min(m, n))而不是 O(m) 或 O(n) 里更差的那个。第二cnt.get(x, 0)是必须的。直接写if cnt[x] 0时如果 x 没在计数器里Python 会抛 KeyError报错报得莫名其妙排查时还容易忽略。如果想更贴近 Java 面试手写也可以看一下这个版本class Solution { public int[] intersect(int[] nums1, int[] nums2) { if (nums1.length nums2.length) { return intersect(nums2, nums1); } MapInteger, Integer counts new HashMap(); for (int n : nums1) { counts.put(n, counts.getOrDefault(n, 0) 1); } ListInteger list new ArrayList(); for (int n : nums2) { int c counts.getOrDefault(n, 0); if (c 0) { list.add(n); counts.put(n, c - 1); } } int[] res new int[list.size()]; for (int i 0; i res.length; i) { res[i] list.get(i); } return res; } }Java 版本的思路一模一样只是把 Python 的 Counter 换成 HashMap。注意 Java 里list.stream().mapToInt(...).toArray()也能达到同样效果但面试手写时我会避免用流因为部分面试官希望看到基础循环写法并且流式代码在小数据量时看不出问题性能敏感场景下反而容易成为争论点。2.3 复杂度分析时间 O(m n)空间 O(min(m, n))设定 m len(nums1)n len(nums2)。建计数器遍历短数组 O(min(m, n))扫描长数组遍历长数组 O(max(m, n))总体时间复杂度 O(m n)空间复杂度主要来自哈希表是 O(min(m, n))输出数组不计入额外空间。这组数字背下来用处很大。面试官问“为什么不用排序解法”你可以直接说当两个数组都无序时哈希法把时间控制在线性级别代价是多用了哈希表的空间。如果题目对空间有限制或者要求原地完成那就换排序双指针。2.4 易错点补充递减到零以后别忘判断我在试跑这类代码时踩过一个典型坑写了if x in cnt:而不是if cnt[x] 0:。前者只能保证元素存在不能保证库存还有。如果 nums1 里 2 只有一次nums2 里 2 有三次用x in cnt会输出三个 2答案错误。另一个隐蔽问题是有人会在循环里删除键if cnt.get(x, 0) 0: result.append(x) cnt[x] - 1这样没问题因为减到 0 后get返回 0不会再进入分支。没有必要写成if cnt[x] 1: del cnt[x]之类删除键反而增加操作还可能让get返回默认值的同时让人误以为元素彻底消失日志调起来多一层困惑。减到零和删除键在语义上有细微差别但在这个题目里减到零就够用了。3. 排序加双指针空间换时间里的另一个极端3.1 思路拆解把无序变成有序扫描一次拿下哈希表方案很快但面试官追问“你能不用额外哈希表吗”时就要亮出排序加双指针。思路分两步分别给两个数组排序用两个指针 i 和 j 分别指向 nums1 和 nums2 的开头比较当前元素。比较时有三种情况nums1[i] nums2[j]说明 nums1 当前元素太小不可能在 nums2 里找到匹配i 前进nums1[i] nums2[j]说明 nums2 当前元素太小j 前进nums1[i] nums2[j]记录这个值i 和 j 同时前进。这个过程的本质是同时扫描两个有序数组谁小谁动相等则同时动自然控制了“次数取较小值”。举例来说nums1 [1, 2, 2, 2]排序后还是这个nums2 [2, 2, 3]排序后还是这个。i 走到第二个 2 时j 已经超过第二个 2后面不会再匹配这就保证了结果最多只有两个 2而不是三个。排序后的数组让重复元素紧凑排列双指针的“谁小谁动”天然是对的。如果数组是无序的这个策略完全失效因为小元素可能出现在后面你无法判断“当前元素太小”是否永远成立。3.2 代码实现核心循环只有几行def intersect(nums1, nums2): nums1.sort() nums2.sort() i, j 0, 0 result [] while i len(nums1) and j len(nums2): if nums1[i] nums2[j]: i 1 elif nums1[i] nums2[j]: j 1 else: result.append(nums1[i]) i 1 j 1 return result这个实现的简洁程度不输哈希表但边界条件更值得小心。while i len(nums1) and j len(nums2)两个条件缺一不可。我见过有人写成while i len(nums1)然后在内部判断if j len(nums2): break虽然也能跑但读起来绕写起来更容易漏。直接维护双条件最稳。排序用原地 sort不复制新数组。Python 的 Timsort 在数组包含大量相同元素时表现很好Java 对 int[] 排序用的是双枢轴快速排序平均 O(nlogn)。算法题场景下直接用语言内置排序就够了手写排序属于自找麻烦还容易出错。3.3 复杂度分析排序是主要成本双指针本身很便宜时间复杂度排序耗时 O(mlogm nlogn)双指针扫描耗时 O(m n)总时间复杂度 O(mlogm nlogn)空间复杂度如果不把排序递归栈算进去双指针只用了 i、j 和 result额外空间接近 O(1)。严格按通用理论快排和 Timsort 都有栈开销通常记为 O(mlogm nlogn) 的排序空间或 O(mn) 的临时空间但很多面试官会接受“额外空间基本 O(1)”的说法因为排序可以在原数组上进行。这个方案适合什么时候用两个数组无序但是对空间敏感或者你能接受耗时换来更低的额外内存。真实面试里两个方案都要能写单纯背一个会显得解题思路不完整。4. 面试进阶三连问这题真正的加分项4.1 数组已经排好序怎么优化这是力扣给出的第一个进阶问题。如果两个数组都已经有序那么哈希表方案就有点“杀鸡用牛刀”了直接双指针 O(m n) 搞定空间 O(1)。排序方案中的“排序”可以直接省掉剩下来的扫描本身就是最优的。如果只有一个数组有序另一个无序那情况要分两种数组长度接近排序无序的那个再用双指针复杂度 O(klogk k)k 是较长的数组长度短数组 vs 长有序数组可以给无序的短数组排序或者逐元素在有序长数组里做二分查找。对短数组的每个元素做二分查找是 O(mlogn)m 小的时候比 O(m n) 更划算。我在面试现场回答这类追问时的顺序是先确认数组是否有序再根据长度关系选择“双指针”还是“短表哈希”或“二分”。不要一上来就报最优解先把前置条件讲清楚这在系统设计类问题里也是同样的表达习惯。4.2 两个数组长度相差悬殊选哪个力扣的第二个进阶问题是如果 nums1 比 nums2 小很多哪种方法更好结论是哈希表法更好但要写成“拿短数组建表”。因为短数组的 HashMap 大小是 O(min(m, n))遍历长数组一次就能把所有交集找出来整体时间 O(m n)。排序加双指针则必须把两个数组都排一遍排序成本是 O(mlogm nlogn)n 很大时非常浪费计算。实际操作时可以先交换两个数组让短数组在前再套用之前的哈希代码。这就是我在 2.2 里先写交换逻辑的原因它不只是一个优化技巧还正好回答了这个进阶问题。如果你非要追求极致可以试试对短数组排序然后遍历长数组时用二分查找或双指针定位窗口。这种做法适合长数组本身有序的场景时间复杂度能压到 O(mlogm nlogm)但代码复杂度比纯哈希高性价比一般。面试中能说出“长度悬殊时哈希表更优”这个结论就够了。4.3 内存受限大数组在磁盘上怎么办这题还有一个非常经典的进阶场景nums2 存储在磁盘上内存装不下。很多人被问到这里就卡住其实考察的是对“内存模型”和“外部排序”的理解。先说一个前提如果小数组能整个进内存那么直接把小数组做成哈希表然后分批读大数组。伪代码如下# 伪代码不代表可直接运行 cnt Counter(小数组) with open(big_array.txt) as f: for line in f: for x in line.split(): if cnt.get(x, 0) 0: result.append(x) cnt[x] - 1这种方案的好处是大数组以流的形式被读取永远不需要一次载入。哈希表占用的内存只跟小数组有关。如果两个数组都大到无法进内存就必须走“外部排序 归并”的路线。流程大致如下把大数组切成多个块每块能读进内存对每块在内存里排序再写回磁盘形成若干个有序小文件使用多路归并把所有有序小文件合并得到全局有序的大数组这个合并过程可以边排序边输出拿到两个全局有序的文件后用两个指针做归并扫描谁小谁前进相等记录并同时前进。外部排序的关键不是“排序算法本身多快”而是“磁盘 IO 次数尽量少”。每轮归并尽可能多地合并已排序块减少磁盘读写轮数。面试中说出分块排序、写回、归并这几步就足以体现对内存受限场景的理解。更深的细节面试官会让你估算 IO 数量那就涉及“多路归并的读放大”不过这道题通常不会追问到那么深。还有一条思路是把交集问题转换成数据库 JOIN对两个数组去重计数再按照共同键做聚合。实际工程里这个方案很常见但算法面试里聊这个容易跑偏回答时分寸要把握好提到外部归并就够了。5. 常见问题与调试实录5.1 哈希表方案翻车实录我在这道题上看到的高频提交错误第一个就是忘记“库存减一”。尤其当 nums2 里某个重复元素特别多时结果会直接溢出正确次数。这种错误在样例nums1 [1,2,2,1]、nums2 [2,2]上不一定暴露因为两边重复次数刚好都是 2一旦改成nums1 [1,1,2]、nums2 [1,1,1,1]就立刻出错。所以写完一定要自己造这种极端用例。第二个高频错误是 KeyError。Python 代码里直接写if cnt[x] 0而 x 不在表里会抛异常。使用get(x, 0)是标准做法也是把“查表”和“查默认值”合成一次操作。记住cnt[x] - 1在 x 存在时是安全的但一旦键被提前删除就会 KeyError所以尽量别在循环里删键。第三个错误是边界情况没处理好。比如nums1 []此时计数器为空扫描 nums2 一个都不匹配结果为空其实代码能正确处理但如果你为了优化手写了交换逻辑要确认交换后的空数组不会导致索引操作。我写的版本里交换逻辑本身不会造成这个问题因为后续只对非空数组的 Counter 查询。5.2 双指针方案翻车实录双指针最常见的 bug 是内层条件写错。我早期写过这样的代码while i len(nums1) and j len(nums2): if nums1[i] nums2[j]: i 1 if nums1[i] nums2[j]: # 错误i可能已经越界 j 1当 nums1[i] nums2[j] 执行 i 1 后下一行还在同一个 if 结构里用 nums1[i]如果 i 已经变成 len(nums1)立刻越界。这个错误非常隐蔽因为有些测试样例恰好不会触发越界只有走到数组末尾才崩。修复方式很简单把第二个 if 改成 elif保证只有第一个条件不成立时才执行第二轮判断。还有一个我个人很推荐的调试顺序先打印 i、j、nums1[i]、nums2[j]每轮循环看一眼。不要看完整结果看其中一轮就行。这样可以立刻发现指针是否跳过头或者进入了死循环。用纸笔模拟三个用例一方为空、一方更短、双方长度一致但重复元素分布不均衡基本能覆盖九成边界问题。5.3 边界用例速查表以下用例是我每次手写完这道题后默认会跑的它们能快速验证程序正确性强烈建议存在本地笔记里用例nums1nums2期望输出说明空数组[][1,2][]一方为空无交集[1,2,3][4,5][]完全没有共同点完全包含[1,2,3][3,2,1][1,2,3]顺序无所谓次数受限[2,2,2][2,2][2,2]取最小次数负数参与[-1,0,3][0,-1,-1][-1,0]哈希表不受负数影响大数重复[100000, 100000][100000][100000]数值大小不影响完全相同[7,7][7,7][7,7]完全相同时长度也相等到表里的最后一种情况容易被忽略一个数组完全等于另一个数组双指针方案里会出现两个指针同时走到底结果长度等于原数组长度程序正确返回所有元素这也能顺带验证 while 循环终止条件。6. 从这道题延伸出去一套解法套路覆盖一串题6.1 相似题型与变式力扣350不是孤立的题它和不少题目共享同一套思考方式349 两个数组的交集把 350 的“计数”变成“存在”用 HashSet 即可88 合并两个有序数组双指针从尾部开始填思路接近排序版双指针剑指Offer 03 数组中重复的数字哈希表计数找重复349 和350一起看能理解“集合”和“多重集合”的区别这个理解在很多设计题里都有用。难度升级后还会看到“两个数组的交集 III”之类的变体可能要求返回最长公共子序列那就要引入动态规划。但350本身只要求连续相等的公共部分不需要跳跃匹配所以双指针足够。想刷透这个知识模块我的建议是把349、350、88、以及“找出所有消失的数字”放在同一批练习。这几道题组合起来覆盖了哈希表、双指针、下标映射三个高频手段。6.2 工程里“数组交集”到底用在哪儿别觉得这题只会出现在面试里。实际业务里“求两个列表的共同元素”太常见了两个用户标签系统的标签重叠部分要算用户相似度会用到集合交集权限系统里判断某个角色是否有某个权限本质是把用户权限列表和资源要求列表做交集日志系统里同一时间段访问过 A 页面和 B 页面的用户ID直接对两个数组求交集就是最简单的漏斗分析推荐系统里把不同召回结果做去重合并本质上也是多集合的交并补。当数据量到达千万级以上就不能再用 Python 的set一把梭了。这时候要引入 Bloom Filter 之类的概率结构先粗筛再做内存映射或外部排序。350 的“进阶”部分恰好就是这些工程问题的简化版。我在公司内部做过一次“共同访问用户”的统计当时两个日志文件各有两千多万行。直接读进内存做哈希峰值内存冲到 3GB机器差点挂掉。后来改成外部排序分块归并内存稳定在 200MB 左右跑完。做完之后我再回头看350才真正理解力扣为什么把“大数组在磁盘上”写成一个进阶问题因为这是真实会撞上的问题。最后再分享一个我自己常用的复盘动作做完350我会额外做一件小事把“哈希法”和“排序双指针”的写题时间各自掐一遍表。哈希法我一般能进两分钟双指针加排序也能在三分钟内搞定。这个时间感觉没什么意义但面试时很管用——脑子里有两条路线就不会因为换一种问法就当场大脑空白。如果你第一次刷这题建议先别打开题解自己花十五分钟写哈希版再花十五分钟写双指针版然后对照本文的进阶问题自问自答一遍。这十五分钟换来的不只是一道题的AC而是一套“数组重叠问题”的完整解题框架。以后遇到再花哨的交集变体你也能一眼看出它是在考计数还是在考指针移动。
