刷 LeetCode 的时候很多人把[leetcode349:两个数组的交集]当成最简单的入门题扫一眼题目就开始写循环能跑通就觉得自己会了。但实际上面试里这道题的水很深它考察的不只是能不能算出交集而是你对数组操作、去重逻辑、时间空间复杂度权衡这些基本功是否真的理解到位。我前后用这道题辅导过不少同学也见过很多人在结果去重空数组边界有序无序这些细节上翻车。这篇文章我会从题目本身的隐蔽要求讲起把哈希集合、排序双指针、二分查找、位图这些解法全部拆开再把面试官真正想看的点和你容易忽略的细节一并说清楚。1. 先读懂题349 的坑点往往藏在描述里1.1 原题到底要求什么LeetCode 349 的中文描述很简短给定两个数组编写一个函数来计算它们的交集。示例也简单比如nums1 [1,2,2,1]nums2 [2,2]结果应该是[2]。看起来人畜无害但题目里有几个决定性约束输出结果中的每个元素一定是唯一的也就是要去重。输出结果可以不考虑顺序。这两句话就是整道题的核心。第一个约束决定了你在返回结果之前必须做去重处理不管用哪种算法重复出现的元素只能保留一次第二个约束给了你极大的自由意味着你可以先排序再比较也可以依赖哈希结构甚至先排序再对其中一个数组去重都不影响正确性。还有一个容易被忽略的点题目没有保证两个数组的长度关系。有可能nums1很长、nums2很短也可能反过来。这一点直接影响了最优解法的选择后面我会专门展开。1.2 为什么 Easy 题也值得复盘很多刷题的人有个误区Easy 题一遍过就赶紧做 Medium觉得复盘是浪费时间。但 349 这类题恰恰是考察基本功是否扎实的高频面试题因为它的解法覆盖了三大类编程思想哈希表/集合的使用对应工程里最常见的查找需求。排序加双指针对应有序数据合并、求交、求并等经典场景。二分查找、位图、分治等进阶思路对应海量数据处理和性能优化。如果你只写了暴力双层循环就跑去看下一题等于把面试中最容易拿分的考察点全丢了。我在实际面试中遇到的候选人凡是能把这道题的边界情况、复杂度分析和变体迁移讲清楚的后面算法题的表现通常也不会差。反过来那些一上来就背模板、却说不清为什么用HashSet而不是List的人往往会在追问环节露馅。2. 三种主流解法拆解从哈希到双指针的思维链路2.1 哈希集合最直观也最稳的答案先给结论哈希集合解法是这道题的首选也是绝大多数工程场景下最通用的方案。思路分两步遍历第一个数组把所有元素放入一个哈希集合。遍历第二个数组如果当前元素已经在集合里就加入结果集合同时把该元素从第一个集合里移除避免结果重复。为什么要加入结果后移除因为题目要求输出唯一元素。如果只判断在不在集合里而不移除第二个数组里重复出现的元素会被反复加入结果你还得额外再开一个结果集合去重。与其事后处理不如在遍历时顺手把已经命中的元素从哈希集合中删掉这样每个元素最多被记录一次逻辑上更简洁空间上也省了一个结果集合。用 C# 写大概是这个样子public int[] Intersection(int[] nums1, int[] nums2) { var set new HashSetint(nums1); var result new Listint(); foreach (var num in nums2) { if (set.Remove(num)) { result.Add(num); } } return result.ToArray(); }这里HashSet.Remove的返回值正好能判断原本是否存在存在时删除并加入结果一步到位。在 Java 里可以用HashSetPython 里直接用集合运算set(nums1) set(nums2)也能一行搞定但是面试时我更推荐你手写遍历逻辑因为这样可以顺便展示你对去重细节的把控。时间复杂度是O(m n)其中m、n是两个数组的长度。空间复杂度最坏是O(min(m, n))取决于你把哪个数组放进哈希集合。这里有个小技巧如果两个数组长度差距很大应该把较短的数组放进哈希集合这样空间占用更小遍历较长数组时每个元素做一次 O(1) 查询总时间仍然是线性的。2.2 排序加双指针适合需要有序结果的场景哈希集合解法虽然快但它返回的结果是无序的。如果题目要求输出有序或者你希望在不使用额外哈希结构的情况下完成计算排序加双指针是更好的选择。思路如下对两个数组分别排序。用两个指针i、j分别指向两个数组的头部。比较nums1[i]和nums2[j]相等记录该值然后i、j同时后移并跳过所有与当前值相同的元素保证结果唯一。小于i后移。大于j后移。任一指针越界循环结束。C 实现vectorint intersection(vectorint nums1, vectorint nums2) { sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); vectorint result; int i 0, j 0; while (i nums1.size() j nums2.size()) { if (nums1[i] nums2[j]) { i; } else if (nums1[i] nums2[j]) { j; } else { result.push_back(nums1[i]); while (i 1 nums1.size() nums1[i 1] nums1[i]) i; while (j 1 nums2.size() nums2[j 1] nums2[j]) j; i; j; } } return result; }这里最需要注意的是跳过重复值的时机。有些版本是先把相等值加入结果再用 while 循环把两个数组中所有相同的连续元素都跳过去有些版本是在找到相等元素后只让i、j同时后移一位让后续的重复元素自然产生nums1[i] nums2[j]的相等判断但这样会导致重复值被重复加入结果因此必须配合跳过重复段的逻辑。我的建议是把跳过逻辑写成独立的 while 循环这样可读性最好也不容易漏。排序加双指针的缺点是排序本身需要O(m log m n log n)的时间好处是如果两个数组本来就有序这一步可以省略直接进入线性比较。很多面试官会追加一个前置条件说数组已经排好序了这时候双指针方案就是标准答案。2.3 暴力法为什么只配用来验证最直接的暴力解法就是双层循环遍历nums1的每个元素再去nums2里查找是否存在存在且没加入过结果就加入结果。时间复杂度O(m * n)空间复杂度取决于结果数组。这种解法在数组长度很小的时候没问题但一旦数据规模到万级就会明显变慢。我的建议是暴力法不要作为正式答案但可以用它来验证其他解法的正确性。实际操作中我会写一个简单的暴力版本作为基准再用随机生成的测试数据对比哈希解法和双指针解法的输出快速确认没有边界错误。这种做法在刷题和写工程代码时都很实用相当于给自己留了一个对照实现。三种主解法的对比解法时间复杂度空间复杂度输出是否有序适用场景双层暴力O(m * n)O(1) 或 O(min(m,n))无序数组极小仅作验证哈希集合O(m n)O(min(m, n))无序通用首选不要求有序排序 双指针O(m log m n log n)O(log m log n)排序栈空间可做到 O(1)有序数组已有序或必须返回有序结果3. 边界条件与数组去重真正拉开差距的细节3.1 空数组、单元素、全相同我见过太多人一上来就写主逻辑完全忽略边界条件最后被测试用例打脸。349 的边界条件其实非常典型建议在写代码前先在脑子里过一遍两个数组都为空返回空数组。一个数组为空另一个非空返回空数组。两个数组只有一个相同元素返回包含该元素的数组。两个数组完全相同返回其中一个数组去重后的结果。两个数组完全不重合返回空数组。数组中存在负数不影响哈希集合和排序比较的逻辑但要注意使用int类型接收负数。用哈希解法时空数组的情况天然被覆盖HashSetint(空数组)是空集合遍历另一个数组时没有任何元素能命中最终结果为空。排序解法同样被覆盖任何一个数组为空while 循环一开始就退出。所以边界条件看似多本质上只要你的主逻辑正确它们会自动通过。但你需要主动说出来因为面试官想听的是你有没有考虑过。3.2 去重逻辑的隐藏要求输出结果中的每个元素唯一这句话很多第一次做这道题的人会理解成对结果数组再调用一次去重方法。这种思路虽然最后结果对但很低效而且暴露了你对去重的本质缺乏理解。去重的本质是当一个元素已经被记为交集结果后同样的元素就不应该再次触发加入结果的动作。不管是哈希解法里的Remove还是双指针解法里的跳过重复段都是在记录结果的同时完成了去重而不是事后清理。这两种思路差在哪里差别在于你是否理解了集合的不重复性是一个约束而不是一个事后补救动作。另外如果你使用 Python 的set(nums1) set(nums2)去重是自动完成的但你要能解释为什么集合运算能保证去重因为集合本身就是无序且不重复的数据结构。面试时如果直接用高等级 API一定要具备向面试官解释底层原理的能力否则会被误认为只会调包。3.3 大数组场景下的内存与时间权衡假设两个数组的长度分别是 1000 万和 1000 万哈希集合解法在时间和空间上都是线性的内存占用大约是存储 1000 万个整数所需空间的好几倍因为哈希表有负载因子、桶数组、节点对象等额外开销。在 C# 和 Java 中每个装箱的Integer或int对象都有对象头内存消耗会进一步放大。这时候有几个工程化的取舍思路如果两个数组都很大但值域有限比如 0 到 100 万用位图代替哈希集合可以把内存压缩到值域长度的 1/8。如果数组大到无法全部载入内存可以考虑外部排序加归并也就是先对两个数组分片排序再流式读取并找出交集。如果只要求判断是否存在交集而不需要返回具体元素可以用更节省空间的方式比如粗粒度布隆过滤器先过滤一轮再精确计算。这些扩展在 LeetCode 上不一定用得上但面试官一旦把题目改成两个超大文件求交集你的思路是否开阔就立刻体现出来了。4. 进阶视野二分、位图与海量数据的工程化思考4.1 二分查找当一方数组远小于另一方哈希集合解法在大多数情况下是时间复杂度最优的但有一个场景例外两个数组长度极端不平衡比如nums1只有 10 个元素nums2有 1000 万个元素。如果仍然用哈希集合你得把 1000 万个元素全部存入集合空间开销很大如果先对小数组排序再遍历大数组时对每个元素在有序小数组里做二分查找时间复杂度是O(m log m n log m)其中m是小数组长度。如果m很小n很大这个方案在空间上几乎只占用小数组的存储实用性很强。Python 里的二分查找可以用bisect模块C 里用binary_search但最稳妥的是自己手写一个二分查找函数。面试中手写二分一定要特别注意循环条件和区间开闭否则很容易死循环或漏掉边界元素。一个常见的坑是使用mid (left right) / 2时如果 left 和 right 很大整型可能溢出正确写法是mid left (right - left) / 2。二分查找方案还需要额外考虑去重如果nums1本身有重复元素直接对每个nums2元素做二分查找无法保证结果唯一所以你要么在二分查找后用一个结果集合自动去重要么在开始前对nums1去重。后者更好因为能减少二分查找的数组长度。4.2 位图法值域受限时的极致压缩位图是处理数组交集的经典手段尤其适合值域已知且不太大的场景。思路是用一个位数组记录某个元素是否出现在第一个数组中元素的值直接映射到位的下标。比如元素5存在就把第5位置 1遍历第二个数组时检查对应位是否为 1是则说明命中。C# 里可以用BitArraypublic int[] Intersection(int[] nums1, int[] nums2) { int maxVal nums1.Concat(nums2).Max(); var bitmap new BitArray(maxVal 1); var result new Listint(); foreach (var num in nums1) { bitmap[num] true; } foreach (var num in nums2) { if (bitmap[num]) { result.Add(num); bitmap[num] false; // 去重 } } return result.ToArray(); }这里bitmap[num] false的作用和哈希解法里的Remove是一样的都是为了确保结果唯一。位图的空间占用是O(值域范围)和时间无关所以如果值域有 10 亿而数组只有 100 个元素位图会非常浪费这时候哈希集合反而更合适。如果值域只有几百万位图几乎是最优解不仅速度快内存也极其紧凑。4.3 海量数据下的外部排序与分治如果两个数组以文件形式存储单机内存放不下哈希集合和位图都不可行。工程上的常规做法是外部排序加归并把大文件拆成多个可以载入内存的分片。对每个分片内部排序然后写回磁盘。对所有有序分片做多路归并得到整体有序的文件。对两个有序文件做归并求交集双指针同时扫描相同的元素输出跳过重复段。这个思路其实就是排序加双指针的海量数据版本。另一个常见思路是哈希分片将两个数组按某个哈希函数映射到多个桶文件相同的元素一定落在同一编号的桶中然后分别对每个桶求交集再合并结果。这种方法的好处是可以在多台机器上并行处理是 MapReduce 风格算法的雏形。这些内容已经超出 Easy 题本身但如果你能在面试中自然带出来说明你有真实的大数据处理经验而不只是刷题选手。不过要注意别过度表现先把基础的哈希解法讲清楚再根据追问逐步深入避免显得答非所问。5. 面试与工程场景中的延伸数组操作的高频套路5.1 面试官可能追问的三个方向我自己模拟面试时最喜欢围绕 349 问这三个问题如果结果要求有序你会怎么做直接切换到排序加双指针并说明排序带来的额外时间成本。如果两个数组非常大内存装不下怎么处理引出外部排序、哈希分片、位图等方案。如果数组元素可能是字符串而不是整数解法有没有变化哈希集合完全不变排序比较则要依赖字符串的字典序位图方案失效因为字符串无法直接映射为连续的整数下标。追问的本质是考察你对数据结构特性的理解而不是考察记忆。所以刷题时不要只记代码要想清楚每个解法的适用条件和失效条件。5.2 从 349 到 350 再到更多变体的迁移LeetCode 350 是两个数组的交集 II要求返回每个元素出现的次数取较小值也就是说结果可以包含重复元素。这道题把唯一性约束去掉后解法核心就变成了计数取最小值用哈希表统计第一个数组中每个元素的出现次数遍历第二个数组时如果当前元素在哈希表中计数大于 0就加入结果并把计数减 1。这和 349 的去重逻辑正好形成对比一个删除元素一个递减计数两者代码结构高度相似完全值得放在一起对照记忆。再往后可以延伸出三道高频变体多个数组的交集可以用逐个两两求交集也可以用哈希表统计每个元素在所有数组中出现的次数达到数组总数时输出。有序数组求交集直接用双指针不需要排序。数组元素范围很大但数量很少可以用哈希集合范围小且密集可以用位图或布尔数组。这些变体在工程里很常见比如多个用户标签列表求共同标签本质上就是多数组交集问题。5.3 实操心得写代码前先想好测试用例最后分享一个我实际刷题和写代码时养成的习惯拿到题目后不要急着写代码先在注释或者草稿纸上列出至少五个测试用例把正常情况、边界情况、极端情况全部覆盖。对于 349我会列这些nums1 [1,2,2,1],nums2 [2,2]期望[2]。nums1 [4,9,5],nums2 [9,4,9,8,4]期望[4,9]。nums1 [],nums2 [1,2]期望[]。nums1 [1,1,1],nums2 [1,1]期望[1]。nums1 [1,2,3],nums2 [4,5,6]期望[]。列完用例再写代码写完后逐条验证。这个过程能帮你发现很多隐藏问题比如我早期用哈希解法时忘记Remove导致结果重复就是因为测试用例没有包含一个数组内部有大量重复元素的场景。后来我把这个习惯固化了不仅在刷题时用在真实项目里排查 bug 时也特别管用。数组相关的题目练多了你会发现所有的高级技巧最后都会回归到数据结构的选择和边界条件的处理这两件事上。349 虽然只是一个 Easy 题但它像一面镜子能照出你对哈希结构、排序、双指针、去重逻辑这些基本功的掌握程度。如果你能把这道题吃透把变体和工程化思路都想明白那么以后再遇到类似的数组交集、去重、合并类问题思路会顺畅很多。