刷 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 哈希集合：最直观也最稳的答案

先给结论：哈希集合解法是这道题的首选，也是绝大多数工程场景下最通用的方案。思路分两步：

1. 遍历第一个数组，把所有元素放入一个哈希集合。
2. 遍历第二个数组，如果当前元素已经在集合里，就加入结果集合；同时把该元素从第一个集合里移除，避免结果重复。

为什么要"加入结果后移除"？因为题目要求输出唯一元素。如果只判断"在不在集合里"而不移除，第二个数组里重复出现的元素会被反复加入结果，你还得额外再开一个结果集合去重。与其事后处理，不如在遍历时顺手把已经命中的元素从哈希集合中删掉，这样每个元素最多被记录一次，逻辑上更简洁，空间上也省了一个结果集合。

用 C# 写大概是这个样子：

public int[] Intersection(int[] nums1, int[] nums2) { var set = new HashSet<int>(nums1); var result = new List<int>(); foreach (var num in nums2) { if (set.Remove(num)) { result.Add(num); } } return result.ToArray(); }

这里HashSet.Remove的返回值正好能判断"原本是否存在"，存在时删除并加入结果，一步到位。在 Java 里可以用HashSet，Python 里直接用集合运算set(nums1) & set(nums2)也能一行搞定，但是面试时我更推荐你手写遍历逻辑，因为这样可以顺便展示你对去重细节的把控。

时间复杂度是O(m + n)，其中m、n是两个数组的长度。空间复杂度最坏是O(min(m, n))，取决于你把哪个数组放进哈希集合。这里有个小技巧：如果两个数组长度差距很大，应该把较短的数组放进哈希集合，这样空间占用更小，遍历较长数组时每个元素做一次 O(1) 查询，总时间仍然是线性的。

2.2 排序加双指针：适合需要有序结果的场景

哈希集合解法虽然快，但它返回的结果是无序的。如果题目要求输出有序，或者你希望在不使用额外哈希结构的情况下完成计算，排序加双指针是更好的选择。

思路如下：

1. 对两个数组分别排序。
2. 用两个指针i、j分别指向两个数组的头部。
3. 比较nums1[i]和nums2[j]：
   • 相等，记录该值，然后i、j同时后移，并跳过所有与当前值相同的元素，保证结果唯一。
   • 小于，i后移。
   • 大于，j后移。
4. 任一指针越界，循环结束。

C++ 实现：

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); vector<int> 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)，空间复杂度取决于结果数组。这种解法在数组长度很小的时候没问题，但一旦数据规模到万级就会明显变慢。

我的建议是：暴力法不要作为正式答案，但可以用它来验证其他解法的正确性。实际操作中，我会写一个简单的暴力版本作为基准，再用随机生成的测试数据对比哈希解法和双指针解法的输出，快速确认没有边界错误。这种做法在刷题和写工程代码时都很实用，相当于给自己留了一个"对照实现"。

三种主解法的对比：

3. 边界条件与数组去重：真正拉开差距的细节

3.1 空数组、单元素、全相同

我见过太多人一上来就写主逻辑，完全忽略边界条件，最后被测试用例打脸。349 的边界条件其实非常典型，建议在写代码前先在脑子里过一遍：

• 两个数组都为空，返回空数组。
• 一个数组为空，另一个非空，返回空数组。
• 两个数组只有一个相同元素，返回包含该元素的数组。
• 两个数组完全相同，返回其中一个数组去重后的结果。
• 两个数组完全不重合，返回空数组。
• 数组中存在负数，不影响哈希集合和排序比较的逻辑，但要注意使用int类型接收负数。

用哈希解法时，空数组的情况天然被覆盖：HashSet<int>(空数组)是空集合，遍历另一个数组时没有任何元素能命中，最终结果为空。排序解法同样被覆盖：任何一个数组为空，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# 里可以用BitArray：

public int[] Intersection(int[] nums1, int[] nums2) { int maxVal = nums1.Concat(nums2).Max(); var bitmap = new BitArray(maxVal + 1); var result = new List<int>(); 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 海量数据下的外部排序与分治

如果两个数组以文件形式存储，单机内存放不下，哈希集合和位图都不可行。工程上的常规做法是外部排序加归并：

1. 把大文件拆成多个可以载入内存的分片。
2. 对每个分片内部排序，然后写回磁盘。
3. 对所有有序分片做多路归并，得到整体有序的文件。
4. 对两个有序文件做归并求交集：双指针同时扫描，相同的元素输出，跳过重复段。

这个思路其实就是排序加双指针的海量数据版本。另一个常见思路是哈希分片：将两个数组按某个哈希函数映射到多个桶文件，相同的元素一定落在同一编号的桶中，然后分别对每个桶求交集，再合并结果。这种方法的好处是可以在多台机器上并行处理，是 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 题，但它像一面镜子，能照出你对哈希结构、排序、双指针、去重逻辑这些基本功的掌握程度。如果你能把这道题吃透，把变体和工程化思路都想明白，那么以后再遇到类似的数组交集、去重、合并类问题，思路会顺畅很多。