202603-找数(luogu-P15799)

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

P15799 [GESP202603 五级] 找数

题目要求

题目描述

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

输入格式

第一行包含两个整数 $n, m$ 。第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$ 表示数组 $A$ 。第三行包含 $m$ 个正整数 $b_1, b_2, \dots, b_m$ 表示数组 $B$ 。

输出格式

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

输入输出样例 #1

输入 #1

3 5
4 2 3
3 1 5 4 6

输出 #1

说明/提示

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

数据范围

对于 40% 的数据，保证 $1 \le n, m \le 1000$ 。
对于 100% 的数据，保证 $1 \le n, m \le 10^5$ ， $1 \le a_i, b_i \le 10^9$ 。

题目分析

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

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

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

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

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

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

综合时间复杂度：极其优秀的 $O(n \log n + m \log n)$ 。

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

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

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

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

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

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

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

示例代码

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

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 解除 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>

int main() {
    // 解除 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>

int main() {
    // 解除 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;
}

代码解析小贴士

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

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年3月17日

202603-有限不循环小数(luogu-P15798)