求两个数组(各自元素互不相同)中共同出现的数的个数。
给定两个数组 A(n 个互不相同的正整数)与 B(m 个互不相同的正整数),请计算有多少个数在 A 与 B 中均出现。
集合哈希表交集快速查找
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m;第二行 A 的 n 个数;第三行 B 的 m 个数 |
| 输出 | 同时在 A 和 B 中出现的数的个数 |
| 数据范围 | 1 ≤ n, m ≤ 10⁵ |
| 数值范围 | 1 ≤ aᵢ, bᵢ ≤ 10⁹ |
| 重要前提 | A 内部元素互不相同,B 内部也互不相同 |
unordered_set,查询平均 O(1)按"先建集合、再查 B"的顺序走一遍。
集合 S = {4, 2, 3}
用哈希集合存储,查询时间是 O(1)
集合建好
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 查询 | O(n + m) 平均 |
| 排序 + 双指针 | A、B 都排序,两个指针同步推进 | O(n log n + m log m) |
| 两重循环暴力 | 对每个 b 扫一遍 A | O(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++; }
A 存入 unordered_set,遍历 B 查询
unordered_set<int> s(a.begin(), a.end()); 然后 for (int x : b) if (s.count(x)) ans++;——两行搞定。两数组分别排序,用两个指针同步推进找相等
| 方案 | 时间复杂度 | 代码量 |
|---|---|---|
| 哈希集合 | O(n + m) 平均 | 约 6 行 |
| 排序双指针 | O((n+m) log(n+m)) | 约 12 行 |
第一行输入数组 A,第二行输入数组 B,程序会找出共同出现的数。
点按钮开始 →
#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; }
| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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) 而超时。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 5 | 2 | 题面样例 |
1 1 | 1 | 单元素且相同 |
1 1 | 0 | 单元素且不同 |
3 3 | 0 | 完全无交集 |
3 3 | 3 | 完全相同的两个数组 |
2 3 | 2 | 大数值,考察哈希(数组开不下) |
count/find 吗?③ 时间复杂度是线性吗?10⁹ 大小的数组会内存溢出。需要为数组 A 建一个哈希集合,占用 O(n) 空间。
✅ 20 万次操作,瞬间完成。如果写成 O(nm),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) 预处理 | 求有序交集、合并有序数组 |
| 集合运算 | 交/并/差 | 集合论类题目 |
unordered_map<int,int> 分别统计两边每个值的出现次数,然后遍历其中一个 map,比较两边计数是否相等。这就从"集合求交"变成了"频次比对"。)