题源洛谷 P15799 [GESP202603 五级] 找数想象一下你有两本通讯录一本记录了班级 A 的同学电话另一本记录了班级 B 的同学电话。现在老师让你找出同时在两个班级通讯录里出现的同学有多少个。你会怎么做一本本翻着比对还是先把所有名字写在一个大本子上看看谁的名字写了两次这道题来自 2026 年 3 月 GESP 五级认证表面上是一个简单的找共同元素问题实际上它考察的是如何用哈希表优雅地实现集合交集运算。本文将带你从朴素的双层循环出发理解为什么哈希表是这类问题的黄金解法并把这个思想沉淀成一个可以复用的算法模板。一、问题本质不是找相同而是数频率很多同学拿到这道题第一反应是对 A 中每个元素去 B 中逐个查找。这个思路在数据范围小的时候没问题——两层循环O ( n × m ) O(n \times m)O(n×m)的复杂度简单直观。但如果n nn和m mm都达到10 5 10^5105这个10 10 10^{10}1010量级的运算量会直接超时。更关键的是题目中有一个容易被忽略的条件两个数组内部的元素互不相同。这个条件意味着什么意味着如果某个数x xx同时在A AA和B BB中出现那么在整个合并后的数据集中x xx恰好出现了两次——一次来自A AA一次来自B BB。这就好比两本通讯录里都没有重名的人那么如果一个名字出现了两次它一定是在两本通讯录里各出现了一次。这道题的核心特征可以概括为以下几点集合交集问题本质是求两个集合的交集大小内部无重复两个数组内部元素互不相同这是关键简化条件频率即答案出现次数恰好为2 22的数就是交集元素离散数据元素值范围可能很大如10 9 10^9109不适合用数组下标直接映射合并统计策略将两个数组统一放入一个频率表而非分别存储再比对所以这道题的本质是利用内部无重复的条件把集合交集问题转化为频率统计问题。二、解题策略一本大账本谁出现两次谁就是交集面对找两个集合的共同元素的问题最自然的思路是统一计数步骤一录入数组 A。遍历A AA的每个元素x xx在哈希表中记录mp[x]。步骤二录入数组 B。遍历B BB的每个元素x xx同样在哈希表中记录mp[x]。步骤三统计频率为 2 的键。遍历哈希表中的所有键值对如果某个键对应的值为2 22说明它在A AA和B BB中各出现了一次计入答案。这个策略的巧妙之处在于我们不需要显式地比较两个数组的元素只需要记账——每个元素来了就记一笔最后看谁的账本上恰好有两笔。这就像两家公司的财务对账不需要逐笔比对明细只需要把两家公司的所有交易记录合并到一个总账里看哪些交易号出现了两次。三、算法模板哈希表统一计数法3.1 算法到底在干什么—— 直觉解释哈希表统一计数法的核心思想可以用一句话概括把两个集合的所有元素倒进同一个大篮子然后数一数哪些元素在篮子里出现了两次。它就像一位细心的图书管理员把两批归还的书统一登记到借还系统里最后查一查哪些书的归还记录恰好有两条——那说明这本书被两个不同的读者借过。在本题中图书管理流程变成收到第一批归还的书数组 A逐本登记收到第二批归还的书数组 B逐本登记查询系统找出归还记录恰好为2 22次的书这些书就是两批归还中共同出现的书3.2 万能模板 —— 伪代码 实战代码伪代码function CountIntersection(A, B): frequency empty hash map for each x in A: frequency[x] for each x in B: frequency[x] count 0 for each (key, value) in frequency: if value 2: count return count实战代码C#includebits/stdc.husingnamespacestd;intmain(){intn,m;cinnm;// 使用 map 作为频率表键为数字值为出现次数mapint,intmp;// 步骤一录入数组 A 的元素for(inti1;in;i){intx;cinx;mp[x];// 该数字出现次数加 1}// 步骤二录入数组 B 的元素for(inti1;im;i){intx;cinx;mp[x];// 该数字出现次数加 1}// 步骤三统计出现次数恰好为 2 的键intans0;for(autox:mp){// x.first 是数字x.second 是出现次数if(x.second2){ans;// 该数字在两个数组中都出现过}}coutansendl;return0;}3.3 例题实现 —— 本题完整代码上面的代码已经是本题的完整 AC 代码。核心流程可以概括为读入n , m n, mn,m和两个数组将两个数组的所有元素统一录入map频率表遍历频率表统计出现次数为2 22的键的个数输出结果以样例为例数组 A{ 4 , 2 , 3 } \{4, 2, 3\}{4,2,3}数组 B{ 3 , 1 , 5 , 4 , 6 } \{3, 1, 5, 4, 6\}{3,1,5,4,6}合并后的频率表数字来源 A来源 B总次数是否交集1 110 001 111 11否2 221 110 001 11否3 331 111 112 22是4 441 111 112 22是5 550 001 111 11否6 660 001 111 11否交集元素为3 33和4 44共2 22个与样例输出一致。3.4 对比实现 —— 双层循环 vs 哈希表理论上双层循环也可以解决这个问题。但哈希表法有明显优势对比维度双层循环哈希表统一计数时间复杂度O ( n × m ) O(n \times m)O(n×m)O ( ( n m ) log ⁡ ( n m ) ) O((n m) \log(n m))O((nm)log(nm))空间复杂度O ( 1 ) O(1)O(1)O ( n m ) O(n m)O(nm)适用数据范围n , m ≤ 10 3 n, m \leq 10^3n,m≤103n , m ≤ 10 5 n, m \leq 10^5n,m≤105甚至更大代码复杂度简单简单Cmap封装完善扩展性差难以处理多集合好可轻松扩展到k kk个集合因此对于集合交集问题当数据范围较大时哈希表是更优选择。3.5 变体清单 —— 这类问题的常见变形变体类型特征描述处理思路数组内部允许重复A 或 B 内部有重复元素先对两个数组分别去重用set再统一计数求k kk个集合的交集有k kk个数组求共同元素统一放入频率表统计出现次数为k kk的键求并集大小统计在 A 或 B 中出现过的不同元素个数频率表中键的总数即为并集大小求差集统计只在 A 中出现但不在 B 中的元素频率为1 11且来自 A 的元素元素范围小如≤ 10 6 \leq 10^6≤106可以用数组下标直接映射用普通数组代替map速度更快需要输出具体交集元素不只是计数还要列出元素遍历时将x.first加入结果数组在线查询动态增删集合元素会动态变化用unordered_set维护支持O ( 1 ) O(1)O(1)增删查3.6 什么时候不能用—— 边界条件和反例这个模板虽然好用但也有明确的适用范围数组内部有重复如果 A 内部有重复如A { 2 , 2 , 3 } A \{2, 2, 3\}A{2,2,3}那么2 22在频率表中的次数会是3 33A 中两次 B 中一次判定条件需要从 2改为 2。最安全的做法是先对两个数组分别去重元素值极大如果元素值达到10 18 10^{18}1018map依然可以处理基于红黑树但普通数组无法开这么大的空间需要保持顺序map会按键排序如果需要保持原数组顺序应使用unordered_map或额外记录顺序内存极度紧张如果n m n mnm极大且内存受限可以考虑先对两个数组排序然后用双指针法求交集空间复杂度O ( 1 ) O(1)O(1)额外空间多组大查询如果有多组询问且数组固定可以预处理排序后用二分查找单次查询O ( log ⁡ n ) O(\log n)O(logn)四、底层逻辑为什么这个算法是对的4.1 无重复条件的威力这道题的关键简化条件在于两个数组内部元素互不相同。这个条件保证了频率与集合归属的一一对应关系如果x xx只在 A 中出现频率 1 11如果x xx只在 B 中出现频率 1 11如果x xx同时在 A 和 B 中出现频率 2 22如果x xx都不出现频率 0 00不会出现在表中这种一一对应关系让我们可以用简单的频率判定替代复杂的集合运算。4.2 哈希表的键唯一性map基于红黑树和unordered_map基于哈希表的核心特性是键的唯一性。当我们执行mp[x]时如果x xx已经存在就增加其值如果不存在就自动创建一个新键。这种自动去重的特性完美契合了集合运算的需求——我们不需要关心x xx之前是否出现过只需要关心它最终出现了几次。4.3 从比对到计数的思维转换这道题最精彩的地方不是哈希表本身而是思维方式的转换从逐个比对两个集合的元素过程导向转变为统一计数后筛选结果导向。这种转换把问题复杂度从O ( n × m ) O(n \times m)O(n×m)降到了O ( ( n m ) log ⁡ ( n m ) ) O((n m) \log(n m))O((nm)log(nm))提升了近1000 10001000倍的效率当n m 10 5 n m 10^5nm105时。这提醒我们在竞赛中怎么做往往不如换个角度看问题重要。五、决策表遇到这类问题怎么选算法场景特征推荐方案原因数据范围n , m ≤ 10 5 n, m \leq 10^5n,m≤105元素离散哈希表统一计数O ( ( n m ) log ⁡ ( n m ) ) O((nm) \log(nm))O((nm)log(nm))代码简洁数据范围n , m ≤ 10 3 n, m \leq 10^3n,m≤103双层循环也可以代码更简单常数更小元素范围小≤ 10 6 \leq 10^6≤106普通数组计数用数组下标映射O ( 1 ) O(1)O(1)访问内存极度受限排序 双指针额外空间O ( 1 ) O(1)O(1)多组查询数组固定预处理排序 二分单次查询O ( log ⁡ n ) O(\log n)O(logn)需要动态增删元素unordered_setO ( 1 ) O(1)O(1)增删查k kk个集合求交集统一频率表判 k一次统计解决所有集合六、工程视角这个思想在实际中有什么用这道题虽然是 GESP 五级的基础题但其核心思想在工程中有广泛应用数据库去重与关联在 SQL 中INNER JOIN操作本质上就是求两个表的交集。数据库引擎内部会使用哈希表Hash Join来高效实现这一操作——先把小表构建成哈希表再遍历大表进行匹配。理解统一计数的思想有助于理解数据库查询优化的底层原理。日志分析与用户画像在数据分析中经常需要找出同时满足两个条件的用户。比如既购买了商品 A 又购买了商品 B 的用户有多少。工程师会把两个购买记录表的数据统一放入一个用户 ID 的频率表然后统计出现次数为2 22的用户——与本题完全同构。推荐系统的协同过滤在电商推荐中找相似用户的核心逻辑是计算两个用户购买商品的交集大小。如果交集越大说明两个用户的品味越相似。这个计算过程就是大规模集合交集运算哈希表是支撑这一算法的核心数据结构。七、小结这道题教会我们的核心认知可以概括为一句话当两个集合内部均无重复元素时集合交集的大小可以通过统一频率统计来求解——出现次数恰好为2 22的元素就是交集元素。用公式化语言总结∣ A ∩ B ∣ ∣ x ∣ count ( x ) 2 , 其中 count 是对 A ∪ B 的统计 ∣ |A \cap B| |\\{ x \mid \text{count}(x) 2, \text{其中 count 是对 } A \cup B \text{ 的统计} \\}|∣A∩B∣∣x∣count(x)2,其中count是对A∪B的统计∣其中count ( x ) \text{count}(x)count(x)表示元素x xx在合并后的数据集中出现的次数。判定条件基于内部无重复的前提x ∈ A ∩ B ⟺ count ( x ) 2 x \in A \cap B \iff \text{count}(x) 2x∈A∩B⟺count(x)2这道题的价值不仅在于它本身更在于它揭示了一类问题的通用解法当问题涉及找共同元素、集合交集时首先观察数据特征——如果集合内部无重复哈希表统一计数是最优雅的解法如果有重复先考虑去重或调整判定条件。在竞赛中这种先观察特征再选择工具的思维方式是高效解题的关键。