GESP 题解库 / 5 级题解 / [GESP202603 五级] 找数 · 第 1 / 23 题
GESP202603 五级 · P15799 · 简单

找数

求两个数组(各自元素互不相同)中共同出现的数的个数。

📊
n, m ≤ 10⁵
数组长度
🔢
aᵢ ≤ 10⁹
数值范围
⚡
O(n + m)
时间复杂度
🎯
哈希集合求交
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定两个数组 A(n 个互不相同的正整数)与 B(m 个互不相同的正整数),请计算有多少个数在 A 与 B 中均出现。

💡
人话翻译:这就是求两个集合的交集大小。最直接的做法:把 A 的所有元素放进一个"哈希集合",然后遍历 B,看每个元素是否在集合里。"互不相同"这个条件很关键——它意味着不存在重复计数的问题,所以答案就是"同时出现在两边"的元素个数。

🔍 关键词提取

集合哈希表交集快速查找

已知条件

项目说明
输入第一行 n、m;第二行 A 的 n 个数;第三行 B 的 m 个数
输出同时在 A 和 B 中出现的数的个数
数据范围1 ≤ n, m ≤ 10⁵
数值范围1 ≤ aᵢ, bᵢ ≤ 10⁹
重要前提A 内部元素互不相同,B 内部也互不相同

需要解决的问题

02
思维导图
整理解题思路的全貌
🔍 集合求交
📥 读入
n、m ≤ 10⁵
A 内部互不相同
B 内部互不相同
值可达 10⁹
🗂️ 建集合
把 A 的元素插入哈希集合
unordered_set<int>
平均插入 O(1)
占用 O(n) 空间
🔁 遍历 B
对每个 b 查询是否在集合中
在 → 计数加 1
avg O(1) 查询
总共 O(m)
⚠️ 易错点
用数组当桶(10⁹ 开不下)
忘记"互不相同"这个前提
用 multiset 导致重复计数
读入用 int 但值可能较大
03
样例手算推导
样例的交集计算

🧮 样例:A = {4, 2, 3},B = {3, 1, 5, 4, 6}

按"先建集合、再查 B"的顺序走一遍。

1
第 1 步:把 A 放进集合

集合 S = {4, 2, 3}

用哈希集合存储,查询时间是 O(1)

集合建好

2
第 2 步:逐个检查 B 的元素

b = 3:在 S 中 ✅ → 计数 1

b = 1:不在 S 中 ❌

b = 5:不在 S 中 ❌

b = 4:在 S 中 ✅ → 计数 2

b = 6:不在 S 中 ❌

✅ 最终计数 2

B 的元素是否在 A 中累计计数
3✅ 是1
1❌ 否1
5❌ 否1
4✅ 是2
6❌ 否2

共同出现的数:3、4,共 2 个 ✓

🔑
为什么"互不相同"这个条件让题目变简单了?如果允许重复,就变成"有多少对 (a, b) 相等"这样的多集问题,需要额外统计每个值在两边的出现次数。而本题保证两边各自无重复,所以"是否同时出现"就是 0/1 判断,直接计数即可。

🧮 两种思路的对比

除了哈希集合,还可以排序后双指针。我们比较一下。

方案做法复杂度
哈希集合A 入集合,遍历 B 查询O(n + m) 平均
排序 + 双指针A、B 都排序,两个指针同步推进O(n log n + m log m)
两重循环暴力对每个 b 扫一遍 AO(nm),10¹⁰ 必然超时
// 排序 + 双指针的写法(不用哈希也能做)
sort(a, a + n); sort(b, b + m);
int i = 0, j = 0, cnt = 0;
while (i < n && j < m) {
    if (a[i] == b[j]) { cnt++; i++; j++; }
    else if (a[i] < b[j]) i++;
    else j++;
}
⚠️
暴力法的代价:n、m 都达到 10⁵ 时,两重循环需要 10¹⁰ 次比较,远超时间限制。看到 10⁵ 这个量级,就要想到用集合或排序把复杂度降到近线性。
04
解法对比
哈希集合 vs 排序双指针

⚔️ 解法对比

🟢 哈希集合(推荐) 推荐

A 存入 unordered_set,遍历 B 查询

  • 平均时间 O(n + m)
  • 代码 6 行
  • 不需要排序
  • 最直观
💡
实现:unordered_set<int> s(a.begin(), a.end()); 然后 for (int x : b) if (s.count(x)) ans++;——两行搞定。

🟠 排序 + 双指针

两数组分别排序,用两个指针同步推进找相等

  • 时间 O((n+m) log(n+m))
  • 代码 12 行
  • 需要额外排序开销
  • 不使用哈希(某些环境更稳)
⚠️
什么时候选它:如果题目还要求"按升序输出交集元素",那么排序法天然满足要求,而哈希法还要额外排序。本题只问个数,哈希法更省事。

📈 性能对比

方案时间复杂度代码量
哈希集合O(n + m) 平均约 6 行
排序双指针O((n+m) log(n+m))约 12 行
05
算法流程图
建集合后遍历另一个数组
开始读入 n、m 和数组 A、B把 A 的所有元素插入哈希集合 Si 从 0 到 m−1,逐个取 B[i]B[i] 在集合 S 中吗?是 ✓答案加 1否 ✗跳过B 的元素都检查完了吗?输出答案结束i 加 1 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔍 交集查找器

第一行输入数组 A,第二行输入数组 B,程序会找出共同出现的数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    unordered_set<int> s;          // 存放数组 A 的元素
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        s.insert(x);
    }

    int ans = 0;
    for (int i = 0; i < m; i++) {
        int x;
        scanf("%d", &x);           // 边读边查,连 B 都不用存
        if (s.count(x)) ans++;     // 在 A 中出现过就计数
    }

    printf("%d\n", ans);
    return 0;
}
🔑
为什么 B 的元素不用存下来?因为题目只要求"总数",读到一个就查一次、立刻计数即可——这叫"流式处理",能省掉一个数组。在数据量很大时,这种写法能显著降低内存占用。

📖 关键几行怎么看

代码作用为什么这样写
unordered_set<int> s哈希集合值可达 10⁹,数组开不下,必须用哈希
s.insert(x)插入把 A 的元素全放进去
s.count(x)查询返回 0 或 1(集合内不重复)
if (s.count(x)) ans++;计数题目保证互不相同,直接计数不会重复
⚠️
两个坑:① 用数组当桶(bool vis[1000000001] 开不下);② 用 multiset 或列表存 A 并逐个查找,会把复杂度退化成 O(nm) 而超时。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 5
4 2 3
3 1 5 4 6
2题面样例
1 1
5
5
1单元素且相同
1 1
5
7
0单元素且不同
3 3
1 2 3
4 5 6
0完全无交集
3 3
1 2 3
1 2 3
3完全相同的两个数组
2 3
1000000000 1
1 1000000000 999
2大数值,考察哈希(数组开不下)
✅
自查清单:① 用的是哈希集合吗?② 查询用的是 count/find 吗?③ 时间复杂度是线性吗?

🚨 易错点清单

⚠️
用数组当桶:aᵢ 可达 10⁹,开 10⁹ 大小的数组会内存溢出。
⚠️
逐个查找代替集合:对 B 的每个元素都扫一遍 A,复杂度 O(nm) 会超时。
⚠️
担心重复计数:题目保证两边各自互不相同,所以不需要额外处理重复。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n + m)
空间复杂度
O(n)
n, m 最大
10⁵
运算量
约 2 × 10⁵

时间怎么算的?

空间都用在哪?

需要为数组 A 建一个哈希集合,占用 O(n) 空间。

✅ 20 万次操作,瞬间完成。如果写成 O(nm),10¹⁰ 次会严重超时。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 集合求交的两种写法
// 写法一:哈希集合(推荐,近线性)
unordered_set<int> s(a.begin(), a.end());
int ans = 0;
for (int x : b) if (s.count(x)) ans++;

// 写法二:排序 + 双指针(要求输出有序交集时更方便)
sort(a.begin(), a.end());
sort(b.begin(), b.end());
vector<int> inter;
int i = 0, j = 0;
while (i < (int)a.size() && j < (int)b.size()) {
    if (a[i] == b[j]) { inter.push_back(a[i]); i++; j++; }
    else if (a[i] < b[j]) i++;
    else j++;
}

// 如果数据范围较小(如 aᵢ ≤ 10⁷),也可以用位图/布尔数组
// bool vis[10000001];

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
哈希集合平均 O(1) 查询判重、求交、两数之和、去重
排序 + 双指针O(n log n) 预处理求有序交集、合并有序数组
集合运算交/并/差集合论类题目
🌟
思考题:如果题目改成"统计有多少个数在 A 和 B 中出现次数相同"(允许重复),该怎么改?(提示:用 unordered_map<int,int> 分别统计两边每个值的出现次数,然后遍历其中一个 map,比较两边计数是否相等。这就从"集合求交"变成了"频次比对"。)