企业官网建设流程全解析

题源：洛谷 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 算法到底在干什么？—— 直觉解释

哈希表统一计数法的核心思想可以用一句话概括：把两个集合的所有元素倒进同一个"大篮子"，然后数一数哪些元素在篮子里出现了两次。它就像一位细心的图书管理员，把两批归还的书统一登记到借还系统里，最后查一查哪些书的归还记录恰好有两条——那说明这本书被两个不同的读者借过。

在本题中，图书管理流程变成：

1. 收到第一批归还的书（数组 A），逐本登记
2. 收到第二批归还的书（数组 B），逐本登记
3. 查询系统，找出归还记录恰好为2 22次的书
4. 这些书就是两批归还中共同出现的书

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++）：

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,m;cin>>n>>m;// 使用 map 作为频率表，键为数字，值为出现次数map<int,int>mp;// 步骤一：录入数组 A 的元素for(inti=1;i<=n;i++){intx;cin>>x;mp[x]++;// 该数字出现次数加 1}// 步骤二：录入数组 B 的元素for(inti=1;i<=m;i++){intx;cin>>x;mp[x]++;// 该数字出现次数加 1}// 步骤三：统计出现次数恰好为 2 的键intans=0;for(autox:mp){// x.first 是数字，x.second 是出现次数if(x.second==2){ans++;// 该数字在两个数组中都出现过}}cout<<ans<<endl;return0;}

3.3 例题实现 —— 本题完整代码

上面的代码已经是本题的完整 AC 代码。核心流程可以概括为：

1. 读入n , m n, mn,m和两个数组
2. 将两个数组的所有元素统一录入map频率表
3. 遍历频率表，统计出现次数为2 22的键的个数
4. 输出结果

以样例为例：

• 数组 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}
• 合并后的频率表：

交集元素为3 33和4 44，共2 22个，与样例输出一致。

3.4 对比实现 —— 双层循环 vs 哈希表

理论上，双层循环也可以解决这个问题。但哈希表法有明显优势：

因此，对于集合交集问题，当数据范围较大时，哈希表是更优选择。

3.5 变体清单 —— 这类问题的常见变形

3.6 什么时候不能用？—— 边界条件和反例

这个模板虽然好用，但也有明确的适用范围：

• 数组内部有重复：如果 A 内部有重复（如A = { 2 , 2 , 3 } A = \{2, 2, 3\}A={2,2,3}），那么2 22在频率表中的次数会是3 33（A 中两次 + B 中一次），判定条件需要从== 2改为>= 2。最安全的做法是先对两个数组分别去重
• 元素值极大：如果元素值达到10 18 10^{18}1018，map依然可以处理（基于红黑树），但普通数组无法开这么大的空间
• 需要保持顺序：map会按键排序，如果需要保持原数组顺序，应使用unordered_map或额外记录顺序
• 内存极度紧张：如果n + m n + mn+m极大且内存受限，可以考虑先对两个数组排序，然后用双指针法求交集，空间复杂度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((n+m)log(n+m))，提升了近1000 10001000倍的效率（当n = m = 10 5 n = m = 10^5n=m=105时）。这提醒我们：在竞赛中，"怎么做"往往不如"换个角度看问题"重要。

五、决策表：遇到这类问题怎么选算法？

六、工程视角：这个思想在实际中有什么用？

这道题虽然是 GESP 五级的基础题，但其核心思想在工程中有广泛应用：

1. 数据库去重与关联：在 SQL 中，INNER JOIN操作本质上就是求两个表的交集。数据库引擎内部会使用哈希表（Hash Join）来高效实现这一操作——先把小表构建成哈希表，再遍历大表进行匹配。理解"统一计数"的思想，有助于理解数据库查询优化的底层原理。

2. 日志分析与用户画像：在数据分析中，经常需要找出"同时满足两个条件的用户"。比如"既购买了商品 A 又购买了商品 B 的用户有多少"。工程师会把两个购买记录表的数据统一放入一个用户 ID 的频率表，然后统计出现次数为2 22的用户——与本题完全同构。

3. 推荐系统的协同过滤：在电商推荐中，"找相似用户"的核心逻辑是：计算两个用户购买商品的交集大小。如果交集越大，说明两个用户的品味越相似。这个计算过程就是大规模集合交集运算，哈希表是支撑这一算法的核心数据结构。

七、小结

这道题教会我们的核心认知可以概括为一句话：

当两个集合内部均无重复元素时，集合交集的大小可以通过"统一频率统计"来求解——出现次数恰好为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

这道题的价值不仅在于它本身，更在于它揭示了一类问题的通用解法：当问题涉及"找共同元素"、"集合交集"时，首先观察数据特征——如果集合内部无重复，哈希表统一计数是最优雅的解法；如果有重复，先考虑去重或调整判定条件。在竞赛中，这种"先观察特征，再选择工具"的思维方式，是高效解题的关键。