【GESP】2026年3月C++ 五级真题解析,luogu-P15799, 找数 | 五级必掌握的三种模板解法

2026年3月，GESP五级真题，考察快速查找（二分查找、集合或双指针），难度⭐⭐★☆☆。洛谷难度级别：普及-。

P15799 [GESP202603 五级] 找数

题目要求

题目描述

给定一个包含  个互不相同的正整数的数组  与一个包含  个互不相同的正整数的数组 ，请你帮忙计算有多少个数在数组  与数组  中均出现。

输入格式

第一行包含两个整数 。 第二行包含  个正整数  表示数组 。 第三行包含  个正整数  表示数组 。

输出格式

输出一个整数，表示在数组  与数组  中均出现的数的个数。

输入输出样例 #1

输入 #1

3 54 2 33 1 5 4 6

输出 #1

2

说明/提示

样例解释样例 1 中，4、3 这两个数字在数组  与  中均出现了。

数据范围

• 对于 40% 的数据，保证 。
• 对于 100% 的数据，保证 ，。

题目分析

这道题目是一道极为经典的"求两个集合交集大小"的问题。在 GESP 五级的考纲中，这是为了专门考察考生彻底摆脱"暴力双重循环"、掌握快速查找算法而设立的标准靶子题。

为什么不能暴力 ？最原始的直觉是：针对  数组里的每一个数，我们都去  数组里从头到尾翻找一遍看有没有。 如果  和  的最大规模只有 （即题目中那 40% 的测试点）， 次运算，一秒内绝对能跑完。 但 100% 的数据点中， 和  高达 。如果还是双重循环， 次运算，这就远远超出了 C++ 一秒钟能跑 1 亿次的常规限制，必定会斩获 TLE（Time Limit Exceeded，超时）。

为了拿到满分，这里提供三种达到普及组五级标准的"降维打击"解法：

解法一：排序 + 二分查找法 (Binary Search)

面对无序的寻找，我们应该先让其中一个数组"列队站好"。

1. 将较长的数组（或者任意一个，假设是 ）使用 std::sort 从小到大排序。代价是 。
2. 遍历另一个数组 ，对于  中的每一个元素，使用二分查找法在排好序的  队伍里迅速定位它是否存在。由于二分查找每次都能砍掉一半的搜索范围，查找一个数只需最多大约  步（）。这一步总代价是 。

• 综合时间复杂度：极其优秀的 。

解法二：黑魔法 STL std::set 集合法

C++ 的标准模板库里有一个自带的高级容器——红黑树集合 std::set。

1. 把数组  的所有元素一股脑塞进 std::set<int> 中。set 的底层会在插入时自动为你维护好一棵平衡二叉搜索树。
2. 遍历  数组，调用内置的 .count() 方法，一指神功瞬间查出  中的数字是否在树里。

• 这种代码写起来最短，非常适合考场上极速通关。

解法三：双指针法 (Two Pointers)

1. 把  和  分别都使用 std::sort 排序。
2. 设置两个排头兵指针 i 和 j，分别指向  和  的开头。
3. 比较两人指着的数字：相等就双双计数并前进；如果  的数字小，就让  的指针 i 往前走去寻找更大的数；反之亦然。就像拉拉链一样，一次就能把两个数组的交集全部摘出。

下面分别给出三种解法的示例代码。

示例代码

解法一：排序 + 二分查找法

#include<iostream>#include<vector>#include<algorithm>intmain(){    // 解除 cin/cout 与 stdio 的同步，加速输入输出    std::ios_base::sync_with_stdio(false);    std::cin.tie(NULL);    int n, m;    std::cin >> n >> m;    // 分别用 vector 存放数组 A 和数组 B    std::vector<int> A(n);    std::vector<int> B(m);    // 读入数组 A    for (int i = 0; i < n; i++) {        std::cin >> A[i];    }    // 读入数组 B    for (int i = 0; i < m; i++) {        std::cin >> B[i];    }    // 第一步：将数组 A 排序，为二分查找打好基础    std::sort(A.begin(), A.end());    int ans = 0;    // 第二步：遍历数组 B 的每个元素，用二分查找去排好序的 A 里"点名"    for (int i = 0; i < m; i++) {        // binary_search 是 C++ 标准库自带的二分查找函数        // 在已排序的 A 中查找 B[i]，找到返回 true        if (std::binary_search(A.begin(), A.end(), B[i])) {            ans++;        }    }    std::cout << ans << "\n";    return 0;}

解法二：std::set 集合法

#include<iostream>#include<set>intmain(){    // 解除 cin/cout 与 stdio 的同步，加速输入输出    std::ios_base::sync_with_stdio(false);    std::cin.tie(NULL);    int n, m;    std::cin >> n >> m;    // 用 set 存放数组 A 的所有元素    // set 底层是红黑树，插入和查找的时间复杂度都是 O(log n)    std::set<int> setA;    // 读入数组 A，逐个插入到 set 中    for (int i = 0; i < n; i++) {        int x;        std::cin >> x;        setA.insert(x); // 插入时 set 会自动去重并排序    }    int ans = 0;    // 读入数组 B，每读一个就去 set 里查一下有没有    for (int i = 0; i < m; i++) {        int x;        std::cin >> x;        // count() 返回元素在 set 中出现的次数（0 或 1）        if (setA.count(x)) {            ans++;        }    }    std::cout << ans << "\n";    return 0;}

解法三：双指针法（Two Pointers）

#include<iostream>#include<vector>#include<algorithm>intmain(){    // 解除 cin/cout 与 stdio 的同步，加速输入输出    std::ios_base::sync_with_stdio(false);    std::cin.tie(NULL);    int n, m;    std::cin >> n >> m;    std::vector<int> A(n);    std::vector<int> B(m);    for (int i = 0; i < n; i++) {        std::cin >> A[i];    }    for (int i = 0; i < m; i++) {        std::cin >> B[i];    }    // 第一步：把 A 和 B 都排序    std::sort(A.begin(), A.end());    std::sort(B.begin(), B.end());    int ans = 0;    int i = 0, j = 0; // 两个指针分别指向 A 和 B 的起点    // 第二步：像拉拉链一样，两个指针同时向前推进    while (i < n && j < m) {        if (A[i] == B[j]) {            // 两边相等，说明找到了一个共同元素            ans++;            i++; // 两个指针都往前走一步            j++;        } else if (A[i] < B[j]) {            // A 当前的数比 B 小，说明 A 的这个数在 B 里不存在            // 让 A 的指针往前走，去找更大的数来匹配            i++;        } else {            // B 当前的数比 A 小，同理让 B 的指针往前走            j++;        }    }    std::cout << ans << "\n";    return 0;}

代码解析小贴士

1. 解法一的核心前提——必须先排序：std::binary_search 在无序数组上会返回错误结果。二分查找的精髓在于"通过有序的大小关系，一次性砍掉一半搜索范围"，使用前必须确保数据已经 sort() 过。
2. 解法二的取舍——代码最短，但常数较大：std::set 底层是红黑树，虽然查找复杂度也是 ，但由于树节点在内存中不连续（缓存不友好），实际运行速度通常比排序+二分查找慢一些。优点是代码极短，适合考场快速通关。
3. 解法三的优雅——双指针一趟扫完： 双指针法要求两个数组都排好序。排序后，两个指针各走一遍就结束了，总的时间复杂度是 ，而且代码逻辑清晰，没有调用任何高级 API，适合加深对排序和线性扫描的理解。
4. 读写加速防 TLE： 代码开头的 std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); 以及用 "\n" 代替 std::endl，在数据量达到  级别时几乎是必备的提速手段。

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。