一、题目概况总结

本次汇报针对洛谷P15799 [GESP202603 五级] 找数题目进行题解总结，该题目是GESP等级考试五级的典型真题，核心考察集合求交与元素存在性查询的算法思路，属于普及-难度的基础算法题，非常适合编程学习者练习数据结构的基础应用。 题目要求为：给定两个分别包含n个和m个互不相同正整数的数组A和B，要求统计同时出现在两个数组中的元素的个数，最终输出统计结果。输入格式为第一行给出两个整数n和m，第二行给出n个正整数表示数组A，第三行给出m个正整数表示数组B；输出为一个整数，代表两个数组的公共元素个数。题目给出的示例输入为3 5，数组A为4、2、3，数组B为3、1、5、4、6，最终输出结果为2，对应公共元素3和4。 从数据范围来看，该题对算法的时间复杂度有明确要求：对于40%的数据，n和m不超过1000；对于100%的数据，n和m最大可达到10^5，且元素大小最大可达到10^9。这要求我们必须选择时间复杂度不超过O(n log n)的算法，暴力双重循环的O(n*m)算法显然无法通过全部测试用例。

二、常见解题思路分析

结合题目要求和数据范围，目前主流的解题思路主要有三种，分别适配不同基础的学习者，各有优劣：

1. 二分查找法

二分查找法的核心思路是先对其中一个数组进行排序，之后遍历另一个数组的每个元素，用二分查找判断当前元素是否在排序后的数组中，统计存在的元素个数即可。具体步骤为：首先将数组A存入数组并完成排序，排序时间复杂度为O(n log n)；之后遍历数组B的每个元素，每次用标准库的lower_bound函数进行二分查找，单次查找时间复杂度为O(log n)，总时间复杂度为O(n log n + m log n)，完全符合10^5数据量的要求，而且不需要额外的复杂数据结构，代码实现简单，依赖C++标准库即可完成，对基础薄弱的学习者非常友好。

2. STL Set集合法

STL Set是C++标准库提供的有序集合容器，天生支持元素去重和O(log n)时间复杂度的存在性查询。具体实现思路为：首先将数组A的所有元素插入Set集合中，插入总时间复杂度为O(n log n)；之后遍历数组B的每个元素，调用count函数判断元素是否存在于Set中，如果存在则计数器加1，最终输出计数器结果即可。该方法代码最为简洁，逻辑清晰，充分利用了STL容器的封装特性，开发效率最高，时间复杂度同样为O((n+m) log n)，完全可以通过全部测试点。

3. 哈希表法

哈希表法的核心思路是利用哈希表O(1)的查询复杂度，将数组A的元素存入哈希表后直接遍历查询。常见实现为使用STL的map或者unordered_map，具体逻辑是将数组A的每个元素对应的哈希计数加1，再遍历数组B每个元素，再次将对应哈希计数加1，最终统计计数为2的元素个数即可；或者直接记录元素是否出现，查询后直接统计。理论上哈希表的平均时间复杂度为O(n+m)，效率会比前两种方法更高，但实际应用中因为哈希冲突的存在，最坏情况下时间复杂度会退化到O(n*m)，而且对于10^9大小的元素，无法直接使用数组标记，必须依赖哈希结构。需要注意的是，有初学者尝试直接开辟大小为1e9的bool数组，这种方法虽然逻辑正确，但会直接占满堆空间导致程序崩溃，是典型的错误实现。

三、解题总结与考点梳理

该题目作为GESP五级的真题，核心考察两个考点：一是元素存在性查询的基础算法思路，要求学习者能够根据数据范围选择合适的算法，避免暴力解法；二是对基础数据结构的应用能力，考察对排序二分、STL集合、哈希表这些常用工具的掌握程度。从难度来看，该题目属于五级考核中的基础题，只要掌握了基础数据结构的用法，就可以顺利完成解答，三种常见解法都可以通过全部测试用例，学习者可以根据自己的熟悉程度选择。 在实际应试中，推荐优先选择二分查找法或者STL Set法，这两种方法时间复杂度稳定，代码实现简单，不容易出现奇怪的运行错误，更适合考场环境；哈希表法虽然理论效率更高，但容易因为哈希冲突或者内存问题出现错误，不推荐基础不牢的学习者在考试中使用。

四、学习意义总结

该题目是编程入门阶段非常经典的集合求交练习题，通过练习该题目，可以帮助学习者理解不同数据结构的适用场景，掌握根据数据范围选择算法的基本思路，为后续更复杂的算法学习打下基础，是GESP五级备考必须掌握的典型题目。