力扣350这道题我印象特别深。刷完349顺手就做它以为把set换成vector就能AC结果提交了一个只通过小部分用例的错误版本。重新读题才反应过来两个数组的“交集”和“交集 II”之间差的是“出现次数”这四个字。这道题在力扣里属于哈希表和双指针的经典入门题也是很多公司面试手撕代码的高频题。它解决的问题很具体给定两个整数数组返回它们的交集并且每个元素在结果里出现的次数要等于原数组中该元素出现次数较小的那个值。比如2在A里出现3次、在B里出现1次结果里只能有一个2。刷透这一题你能把哈希计数、排序扫描、双指针、复杂度分析串在一起面试官最常见的“如果输入已排序怎么办”“数据太大内存放不下怎么办”也都能从这题出发回答。适合正在做力扣数组类题目或者准备面试但一直分不清349和350区别的读者。1. 先拆透题目两个数组的交集 II 到底要什么1.1 题目描述与次数取较小的规则力扣350的题面其实很短给定两个整数数组 nums1 和 nums2返回它们交集的结果结果中每个元素出现的次数应与该元素在两个数组中出现的次数一致。如果某个元素在一个数组中出现3次、在另一个数组中出现1次结果里只出现1次输出顺序不做要求。先看两个力扣给的示例nums1 [1,2,2,1]nums2 [2,2]返回 [2,2]。这里 2 在两边都出现 2 次取较小值仍是 2所以结果里要有两个 2。nums1 [4,9,5]nums2 [9,4,9,8,4]返回 [4,9] 或 [9,4]。9在nums1出现1次、在nums2出现2次取较小值为1所以只能输出一个94同理。这里有个新手容易忽略的点“顺序无所谓”意味着我们不需要保持原数组的元素先后顺序。这一点很重要它让实现自由度大了很多。你完全可以把匹配到的结果乱序输出力扣判题只看集合内容和次数是否一致不看元素相对顺序。1.2 和 349 的差异是本题最大的坑349题“两个数组的交集”要求输出去重后的公共元素每个值最多出现一次350题要求输出带次数的交集每个值可以出现多次次数取两边的最小值。我见过不止一个同事在面试时把这两题混着讲。差异直接体现在解法上349用两个 unordered_set 就能判定交集350如果把 nums1 放进 set 再扫描 nums2nums1 里出现多次的相同值在 set 里只剩下一个“存在标记”结果次数就会完全被 nums2 的重复次数带着跑。比如 nums1 [2,2]nums2 [2,2,2,2]set 法会把四个2全部输出正确结果却只有两个2。下面用表格对照更清楚维度349 两个数组的交集350 两个数组的交集 II交集含义去重后的公共元素带次数的公共多重集关键处理判断是否存在计数并取最小值结果中重复值每种值最多一个每种值可重复次数取 min常用工具unordered_setunordered_map 或排序双指针所以做这题的第一步不是急着写代码而是先确认重复值要不要保留次数要不要取 min这两个问题想清楚后面的解法就是顺水推舟。2. 暴力解法与思考过程不写哈希能不能做2.1 双层遍历加标记的朴素实现如果没有学过哈希第一反应通常是双重循环拿 nums1 的每个元素去 nums2 里找找到一个就把它加入结果同时把 nums2 里那个位置标记为“已使用”避免同一个位置被后面重复匹配。注意这里不能只判断“nums2 里是否存在”。比如 nums1 [1,2,2,1]nums2 [2,2]如果只判断存在遍历 nums1 时会因为两个2都存在而输出 [2,2]这碰巧对了但遇到 nums1 [2,2]nums2 [2,2,2,2] 就会出问题。暴力解法里也必须维护“消耗”状态通常用一个 vector used 来标记 nums2 对应位置是否已经被匹配过。每匹配成功一个就把对应位置 used[j] 设为 true后续循环跳过 used[j] 为 true 的位置。这里有一个实现细节值得说为什么不用 erase 删除已匹配元素因为 vector 的 erase 会把后面的元素整体前移单次删除是 O(n)频繁删除会让总复杂度再上一个台阶。用标记数组比删除元素更适合暴力解法也更容易调试。2.2 暴力方法的复杂度为什么扛不住暴力解法的两层循环最坏情况下要比较 m*n 次。m 和 n 都是 10^4 的量级时比较次数就是 10^8在力扣的严格评测下基本超时。如果两个数组都到 10^510^10 次比较完全不可接受。所以暴力法只适合小数据或者在纸上推演思路真正提交还是要回到 O(mn) 或者 O(m log m n log n) 级别的方法。但暴力思路并不是白费。它让你理解了“消耗”这个词的含义每个匹配到的元素在原数组中对应的那一次出现要被用掉不能反复使用。后面哈希表法里的“计数减一”、双指针法里的“同时向前移动”本质上都是在实现这个消耗逻辑。3. 哈希表计数法最稳的 O(mn) 解法3.1 核心思路统计短数组消耗式匹配长数组哈希表计数法的核心两句话先统计一个数组中每个元素出现的次数再遍历另一个数组每遇到一个“计数大于 0”的元素就输出并把计数减一。为什么选较短的数组做统计这里有一个很重要的空间优化。如果两个数组长度分别是 m 和 n且 m n用较短的数组建哈希表最多只会产生 m 个键值对然后遍历较长的数组去匹配。这样空间复杂度是 O(min(m,n))而不是 O(max(m,n))。很多人在面试时忽略这一点但只要答出来就是一个明显的加分项。匹配的过程可以理解成“消耗”每个元素在原数组里能匹配的次数是有限的。比如 nums1 里的2有2个哈希表里计数为2遍历 nums2 时碰到第一个2输出并减为1碰到第二个2输出并减为0第三个2再来时计数已经是0就不会被输出。这个“减一”动作就是满足题目“次数取最小值”的关键。顺带说一下为什么不推荐用 multiset 来做。有人会想把 nums1 放进 multiset然后遍历 nums2每次 find 到就把它从 multiset 里删除一个。逻辑上说得通但 multiset 的查找是 O(log n)删除又要小心迭代器失效节点开销也比哈希表大。相比之下 unordered_map 的均摊 O(1) 查找明显更快代码也更清晰。3.2 C 代码实现与三个关键细节上 C 代码class Solution { public: vectorint intersect(vectorint nums1, vectorint nums2) { // 让较短的数组作为统计对象节省哈希空间 if (nums1.size() nums2.size()) { swap(nums1, nums2); } unordered_mapint, int count; count.reserve(nums1.size() * 2); for (int x : nums1) { count[x]; } vectorint ans; for (int x : nums2) { auto it count.find(x); if (it ! count.end() it-second 0) { ans.push_back(x); --it-second; } } return ans; } };三个细节reserve 提前分配如果知道大概要放多少键值对提前 reserve 能减少扩容时的 rehash 开销。刷题时数据量不大这只是锦上添花但能体现你对容器底层机制的理解。用 find 而不是 operator[]operator[] 在键不存在时会插入一个默认值为 0 的新键这样遍历 nums2 时那些从不曾在 nums1 出现的值也会不断插入新键污染哈希表。用 find 只查找不插入更干净。一定要做 it-second 0 的判断计数为 0 表示 nums1 里的该值已经消耗完不能再输出。有人只判断 it ! end 就 push结果会把超额的重复值也输出。注意这里的 --it-second 是允许的因为迭代器指向的是 map 中的元素修改 value 不会影响迭代器本身的有效性。3.3 时间与空间复杂度分析时间上统计短数组需要遍历一遍O(min(m,n))匹配长数组需要遍历一遍O(max(m,n))总体 O(mn)。unordered_map 的查找和插入在均摊意义下都是 O(1)所以整体是线性的。空间上哈希表最多存放 min(m,n) 个键值对即 O(min(m,n))这还不含输出数组。输出数组最多有 min(m,n) 个元素但一般不计入算法复杂度。哈希表的上限在建表时已经确定是短数组的所有不同值所以即使长数组里有超多重负哈希表也不会变大。这就是选短数组做哈希的额外好处。3.4 顺手给一个 Python 版本如果刷题用 Python代码更短。这里用 Counter 来统计注意取数时用 get 防止 KeyErrorfrom collections import Counter class Solution: def intersect(self, nums1: List[int], nums2: List[int]) - List[int]: if len(nums1) len(nums2): nums1, nums2 nums2, nums1 cnt Counter(nums1) ans [] for x in nums2: if cnt.get(x, 0) 0: ans.append(x) cnt[x] - 1 return ansPython 的 Counter 底层也是哈希表逻辑和 C 版本完全一致。需要注意如果直接写 cnt[x] 0当 x 不在 Counter 里时不会报错而是返回 0但如果后续直接 cnt[x] - 1会给其中插入 0 或负数造成冗余键所以用 get 更干净。4. 排序加双指针不用额外空间也能过4.1 什么时候优先选双指针哈希表法看起来已经很完美但它有一个“额外空间”的缺点以及一个“没有利用有序信息”的缺点。如果面试官要求“不用额外数据结构”或者输入本身就是有序数组排序双指针方案就更有优势。原题并没有说数组已排序所以需要先调用 sort。这个排序并不可怕C 标准库的 sort 是 introsort快速排序 堆排序的混合递归过深会自动切到堆排序平均复杂度 O(n log n)最坏也不会退化到 O(n²)对 10 万级别的数据非常快。另一种场景是内存紧张不想额外开一个哈希表只希望在原数组或拷贝上进行扫描那双指针方法也是更合适的选择。面试时先问自己一句输入数组能不能先排序如果能双指针就是比哈希更省内存的答案。4.2 排序后指针推进的原理双指针法的核心是先让两个数组从小到大排好然后各用一个指针从头部开始扫描。拿 nums1[i] 和 nums2[j] 比较nums1[i] nums2[j]说明 nums1 当前值太小nums2 里已经不存在比它更小的值了那么 nums1[i] 不可能出现在交集里i 右移。nums1[i] nums2[j]对称地nums2[j] 太小j 右移。两者相等说明找到了交集元素输出它i 和 j 同时右移。为什么相等时一定要同时右移因为每个元素在两个数组中能被匹配的次数有限输出一个就消耗掉两边各一个。如果只移动一边可能会出现重复匹配同一个位置的值导致输出次数超过 min。前面暴力解法里强调的“消耗标记”在双指针里变成了“同时右移”这个简单动作。这个思路有点像两个人各拿一打卡片按编号排好序同时从第一张开始对谁编号小谁先出下一张编号一样就记一次并双方同时换下一张。它和合并两个有序数组的归并思想也很接近只是合并时把相等值写进结果数组而这里只保留相等值。4.3 C 实现与边界自测上代码class Solution { public: vectorint intersect(vectorint nums1, vectorint nums2) { sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); int i 0, j 0; vectorint ans; while (i nums1.size() j nums2.size()) { if (nums1[i] nums2[j]) { i; } else if (nums1[i] nums2[j]) { j; } else { ans.push_back(nums1[i]); i; j; } } return ans; } };写完先给三组边界用例自查空数组nums1 为空时i0 不小于 size直接跳过 while返回空数组。完全没有重复[1,2,3] 和 [4,5,6]比较过程中较小的那个指针一直前移直到某一边数组走出边界结果为空。一个数组包含另一个数组的所有元素[1,2,3] 和 [1,1,2,2,3,3]两个指针会不断同步推进一旦一方耗尽就退出结果自然包含所有能匹配的元素。4.4 复杂度分析与面试追问双指针法的复杂度要拆成三部分排序本身是 O(m log m n log n)两个指针扫描是 O(m n)总体取最大开销。所以虽然扫描是线性的排序却让整体变成 O((mn) log (mn)) 级别。空间上它赢了除了输出数组只用了常数个指针变量答案是 O(1)。如果面试官问“输入已经有序”那排序的 log 部分直接消失整体变成 O(mn)这是最优的。如果面试官再问“能不能不修改原数组”那就先复制一份再排序相当于用 O(mn) 空间换原数据不被破坏。多说一句如果你刷的是 Java注意 Arrays.sort 对基本类型用的是双轴快速排序对对象用的是 TimSort而 C 的 sort 要求随机迭代器introsort 在绝大多数情况下性能很稳。不同语言排序实现的差异不会影响这道题的正确性但会影响常数时间比如在极端逆序数据下C 的 sort 也基本不会退化可以放心用。4.5 哈希法和双指针法怎么选用一张表把两个方案的关键差异列出来方便面试时“一句话说清楚”维度哈希表计数法排序双指针法时间复杂度O(mn)O(m log m n log n)空间复杂度O(min(m,n))O(1)是否修改原数组不修改排序会修改输入已排序时复杂度不变可降到 O(mn)适合场景数据乱序且内存充足内存受限或输入已排序说人话的选型建议笔试刷题为了稳过哈希写法不容易漏细节面试手撕代码时先问数组是否有序有序直接双指针无序可以先答哈希再顺带提一句“如果不希望用额外空间可以排序后双指针”这种权衡分析往往比代码本身更能打动面试官。5. 面试必问的三种进阶变形5.1 输入已经排好序时怎么优化这是力扣题目下方最经典的 follow-up如果给定的两个数组已经排好序如何优化算法答案很简单直接跳过 sort沿用双指针法此时时间复杂度 O(mn)空间复杂度 O(1)。为什么不用哈希哈希也是 O(mn)但空间要额外花 O(min(m,n))而且完全浪费了“有序”这个免费信息。双指针利用有序性把比较范围不断缩小本质上是线性归并的思想。这个点面试被问到就是送分题前提是你知道双指针法。如果只背了哈希解法这一问可能直接卡住。5.2 三个数组求交集怎么做如果题目升级成三个数组比如 nums1、nums2、nums3返回三者交集次数上也要取三者中的最小次数。方法可以结合哈希先用哈希表统计第一个数组每个元素的次数然后遍历第二个数组只保留“计数大于 0”的元素并递减计数得到两个数组的交集再用同样逻辑与第三个数组做一次。这样写简单直白但需要两轮中间结果。如果三个数组都已排序可以用三个指针同时扫描谁指向的值最小谁就推进三个值相等才输出并同时推进。这其实就是双指针扩展成多指针也很适合现场手撕。如果数组个数不是固定 3 而是 k可以循环用两个数组合并或者统计每个值在所有数组中出现的总次数最后只输出“出现次数等于数组个数”的值。这几种方案复杂度差异并不大关键是让面试官看到你能把双指针思路推广到更多路。5.3 内存不够放不下全部数据怎么办另一个经典 follow-up如果 nums1 非常大无法一次性放进内存但 nums2 比较小能全部载入怎么办这时候哈希表法反而是最合适的用 nums2 建哈希表然后流式读取 nums1逐元素匹配递减即可。注意这里的选择逻辑和“让短数组做哈希”一脉相承——小的能进内存大的在外面流式读。如果两个数组都大到内存放不下常规手段是分桶哈希或外部排序。分桶哈希的做法是选定一个 K把每个元素按 hash(x) % K 分到 K 个桶里写进 K 个临时文件因为交集只会出现在同一个桶的内部两边都落在同一个桶的值才有可能相等所以可以逐桶读入内存做交集把每个桶的结果汇总就是最终答案。外部排序双指针则是把两个数组分块排序后写入磁盘再用归并的方式顺序读取比较。这两种都是海量数据处理里的常用套路面试能讲出名词和大致过程就足以拉开差距。5.4 大次数差异用例下两种方法的表现补充一个不太被注意的测试点如果同一个值在一边出现特别多次比如 nums1 里有一万个 1nums2 里只有两个 1。哈希表法里nums1 建表后计数是 10000遍历 nums2 时命中两次输出两个 1、计数减到 9998逻辑正确排序双指针法里排序后两个数组的 1 都连续排列指针会从两边的第一个 1 开始同步前进直到较短的数组里没有 1 为止同样会输出两个 1。两种方法在这种极端用例下都不会翻车。但如果你用 349 那种 set 思路就会因为 nums1 的 set 只有“1 存在”这个信息导致输出完全取决于 nums2 里有多少个 1。这里再次提醒理解“消耗/次数”语义是这题最重要的护身符。6. 常见错误与排查技巧实录6.1 把 349 的去重逻辑直接搬过来这是最典型的错误我自己就犯过。错误代码长这样vectorint intersect(vectorint nums1, vectorint nums2) { unordered_setint s(nums1.begin(), nums1.end()); vectorint ans; for (int x : nums2) { if (s.count(x)) { ans.push_back(x); } } return ans; }如果 nums1 [2,2]nums2 [2,2,2,2]这段代码会输出四个 2但正确答案是两个 2。因为 set 只记录了“2 存在”没有任何关于 nums1 里 2 到底有几个的信息。排查这类问题时建议先构造“两边重复次数不一致”的用例它能一秒钟暴露几乎所有次数相关的错误。6.2 匹配之后忘记递减计数哈希表法常见的第二个错误是找到了就 push但没有对 map 里的计数执行减一。比如拿到 it ! end 就直接 push_back(x)完全不管 it-second 剩余次数。这样 nums1 里只出现一次的值会因为在 nums2 里出现多次而被重复输出。解决方法是永远记住那句口诀匹配一次消耗一次。递减操作不是可选项它是这题“次数取最小值”语义的直接实现。写完代码后硬编码跑一个 nums1 [1]nums2 [1,1,1] 的用例如果结果输出三个 1那一定是忘了减一。6.3 双指针自增写错导致死循环双指针法最常见的 bug 是把相等的分支写成只增加一个指针。比如} else { ans.push_back(nums1[i]); i; // 忘了 j }这段代码不会稳定地死循环但可能会反复输出同一个值或者因为 nums1[i] 变大跳进另一个分支导致逻辑混乱。自测时把两个一样长的数组 [1,2,3] 和 [1,2,3] 跑一遍就能发现结果异常。养成一边提交一边检查指针移动对称性的习惯能省很多调试时间。6.4 空数组与全不匹配的边界用例空数组用例nums1 或 nums2 为空理论上结果应为空。哈希表法遍历空数组不进入循环双指针法 while 条件第一次就不满足都能自然返回空数组。但很多人在本地测试时只测了非空用例提交后才被 case 打脸。全不匹配的用例比如 [1,2,3] 和 [4,5,6]也要跑一遍确认返回的是空数组而不是错误输出。写算法题时边界用例和反例这两个习惯越早培养越好。6.5 值域很大或含负数时别用定长数组看到值域很小就把元素当作数组下标统计这种做法只适合“值域范围明确且不大”的情况例如元素在 0 到 1000 之间。一旦题目没有说明值域而数组中可能包含负数、int 最大值或者跨度极大用定长数组就会有两个问题一是负数无法直接作为下标需要做偏移二是值域太大时根本开不出那么多空间。哈希表不关心值域任意整数都能作为键所以在力扣这类通用题里优先写 unordered_map 而不是定长计数数组。这也是“算法题要多想一层”的典型例子看起来更省事的数组下标方案往往暗藏着值域陷阱。7. 测试用例验证与实战选型建议7.1 用四组用例跑一遍两种解法准备四组用例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[1,2,3]nums2[4,5,6]期望输出空。nums1[2,2]nums2[2,2,2,2]期望输出 [2,2]。哈希法在第 4 组用例上的执行过程nums1 建表后 count[2]2遍历 nums2 时遇到前两个 2 分别输出并减计数第三个 2 来时 count[2] 已经是 0不会输出最终结果正好两个 2。双指针法排序后再看也是输出两个 2 后指针走到短数组尽头。如果本地调试跑出这四组用例全部通过这道题的正确性基本就不用担心了。7.2 一道题能覆盖哪些面试知识点这道题虽然难度不高但覆盖的知识点密度非常高哈希表的基本操作和空间优化、排序算法复杂度、双指针扫描、输入有序时的算法裁剪、内存受限时的分桶思路。面试官从这一题出发可以连续追问五六轮很多人栽在“为什么这里用哈希”“为什么选短的做哈希”这种看似简单的问题上。准备面试时别只满足于 AC把代码里的每个选择都问一遍为什么。如果还想继续练同类型的题可以先把 349 和 350 放在一起对比再做合并两个有序数组、区间合并这类双指针题最后试试三数组交集的变体。这些题目连起来刷一遍比单独刷十道数组题印象都深因为它们的底层思想是相通的。7.3 实战里到底该用哪种写法我的实战建议是分场景。笔试或竞赛刷题优先哈希表法O(mn) 耗时最稳代码也不容易出边界问题。面试手撕代码先口头确认输入是否有序。有序直接双指针无序则先给哈希方案再补充“如果想省空间可以排序后双指针”让面试官看到你不只会背模板。数据规模大、内存紧张回到分桶哈希或外部排序能讲清楚思路就足以证明你是真的懂原理。这个选型不是死规则核心是理解每种方法的复杂度来源然后根据实际情况取舍。哈希法强在时间和无序场景双指针强在空间和有序场景二者互补而不是互斥。我个人刷这道题最大的体会是代码写错之后不要急着看题解先造两个“重复次数不一致”的用例跑一遍很快就能定位到是 set 去重的问题、还是忘了递减计数的问题。把 349 和 350 放在一起对比着做一遍比单独刷十道数组题印象都深。后来我再做区间合并、有序数组归并这类题目发现用的还是这里练熟的双指针思想。如果你正在准备面试建议把这一题当作“哈希与双指针的分水岭”来对待。弄懂了为什么“匹配一次消耗一次”为什么“相等时两个指针都要动”后面很多数组题都会顺畅很多。哪怕时间紧至少把两种解法手写一遍再对着 5.1 和 5.3 的两个追问自己讲一遍这一题就算吃透了。