1. 题目到底在考什么
先说结论：AcWing 2951「不重复数字」不是一道难题，但它非常典型。它考察的核心只有一件事：在数据量较大的情况下，如何快速判断一个数是否已经出现过。听起来很简单，但很多人在初次接触这道题时，会本能地想到一种最朴素的做法，然后直接超时。
这里直接点明几个关键信息，方便还没做过的人对照：
- 题号：AcWing 2951
- 题目名：不重复数字
- 常见标签：哈希表、离散化、去重、卡常优化
- 适用人群：刚学完基础算法的初学者、准备蓝桥杯或CCF CSP的选手、想复习哈希表应用的老手
题目本身很短，一般描述是：给定若干个整数，要求按顺序输出这些数中第一次出现的那些数，也就是把重复出现的数字去掉，只保留第一遍出现的那个。比如输入1 2 1 3 2，输出就是1 2 3。听起来和“数组去重”完全一样，但它恶心的地方在于数据范围：数的个数可能很大，数值本身也可能很大，甚至可能包含负数。
所以这道题真正的价值不在于“你会不会去重”，而在于“你会不会在有限的时间和空间内去重”。
2. 为什么不能直接开数组标记
2.1 数值范围太大，数组开不下
很多新手第一反应是：开一个bool visited[1000000000]，每次读到数字x，就看看visited[x]是不是true。这个思路本身没错，但现实很骨感。
如果题目给的数值范围是0 <= a_i <= 10^9，你要开一个长度十亿的bool数组。在C++里，bool数组虽然每个元素只占1字节，但十亿字节就是1GB左右。多数在线判题系统的内存限制是64MB、128MB或者256MB，直接开数组等于提交前就宣告失败。
就算你用bitset压缩一下，一个bitset<1000000000>也只占用约125MB，依然可能超出限制。而且题目还可能出现负数和超大正数，数组下标的天然限制让这条路彻底走不通。
2.2 用普通数组现炒现卖不行
还有同学说：那我用一个普通数组，每读到一个数就遍历一遍已经保存的数组，看有没有出现过，没有就加进去。这样空间不炸，时间炸了。
假设总共n个数，每个数都不同，那么第i个数需要和前面i-1个数比较，总比较次数大约是1+2+3+...+(n-1)，也就是n(n-1)/2，复杂度 O(n^2)。如果把n放到10万甚至100万量级，O(n^2) 基本等于TLE。
所以，这题的突破口只有一个：在常数时间内完成“查询是否出现过”。
3. 哈希表为什么是正解
3.1 哈希表的本质
哈希表的核心思想是：给定一个值x，通过哈希函数hash(x)把它映射到一个固定范围内的整数下标，然后直接去数组的对应位置查看。
这个“查看”操作的平均复杂度是O(1)，而且是读写都O(1)。比 O(n) 遍历快得多，比 O(log n) 二分查找也要快。
生活化类比：你去超市存包，储物柜上有一个编号，你把包放进2号柜，手里拿着一张写着2的纸条。取包时你直接走到2号柜打开，不需要从1号柜挨个看到100号柜。哈希表就是那个“写着编号的纸条”。
3.2 哈希冲突
不同值可能映射到同一个位置，这就叫哈希冲突。比如hash(x) = x % 7，那么 x=7 和 x=14 都会落到0号位置。
解决冲突的常用方法有两种：
- 拉链法：数组每个位置挂一个链表，冲突的多个元素都挂在这个位置后面。
- 开放寻址法：如果目标位置被占，就往后找下一个空位，依次探测。
竞赛里处理整数哈希，我个人最喜欢用开放寻址法，因为实现简单、常数小，而且容易用好。拉链法需要建链表，代码量稍微多一点。
3.3 C++里怎么实现
C++标准库提供了std::unordered_set和std::unordered_map，底层就是哈希表。这道题用unordered_set就够了。
#include <iostream> #include <unordered_set> int main() { int n; while (std::cin >> n) { std::unordered_set<int> seen; bool first = true; for (int i = 0; i < n; i++) { int x; std::cin >> x; if (!seen.count(x)) { if (!first) std::cout << ' '; std::cout << x; first = false; seen.insert(x); } } std::cout << '\n'; } return 0; }核心逻辑就五行：
- 读取一个数x
- 判断
seen.count(x)是否为0 - 为0说明第一次出现，输出它，并插入
seen - 不为0说明重复，跳过
- 注意格式：数字之间用空格隔开，行尾不能有多余空格
这个写法非常直白，适合大多数人。但我必须提醒一句：在线OJ上，unordered_set不一定是最稳的。有的环境哈希策略奇葩，最坏情况下可能退化成O(n^2)。后面会讲更稳妥的替代方案。
4. 手写哈希表方案
4.1 为什么值得手写
不写标准库反而要手写哈希表，有以下几个原因：
- 有些题目环境不支持C++11，
unordered_set用不了 - 手写开放寻址法性能更高，尤其在卡时间的题里
- 手写哈希能够更直观地理解“哈希冲突”到底发生了什么
这题如果给0.5秒时限，我会毫不犹豫选择手写。
4.2 完整的开放寻址法模板
思路：开一个大一点的数组h，初始化为一个不可能出现的标记值。这里我用N = 2000003，因为数据总量大概在100万级别左右，开到两倍以上能明显降低冲突概率。
#include <iostream> #include <cstring> const int N = 2000003; const int EMPTY = -1e9 - 1; int h[N]; int find(int x) { int k = (x % N + N) % N; while (h[k] != EMPTY && h[k] != x) { k++; if (k == N) k = 0; } return k; } int main() { int t; std::cin >> t; while (t--) { int n; std::cin >> n; memset(h, 0x3f, sizeof(h)); // 因为后面用EMPTY比较，memset方式需要调整，这里改用循环初始化 for (int i = 0; i < N; i++) h[i] = EMPTY; bool first = true; for (int i = 0; i < n; i++) { int x; std::cin >> x; int pos = find(x); if (h[pos] != x) { h[pos] = x; if (!first) std::cout << ' '; std::cout << x; first = false; } } std::cout << '\n'; } return 0; }解释几个关键点：
k = (x % N + N) % N：这里取模后加N再取模，是为了处理负数。如果x是负数，直接x % N结果是负的，会导致数组下标越界。while循环解决冲突：如果当前位置被占用且不是x，就往后探测。直到找到空位，或者找到和x相等的值。return k不管是找到空位还是找到旧值，返回的k都能让主函数判断实际结果。h[pos] != x说明这个数第一次出现，否则说明已经出现过了。
4.3 为什么N要取质数
哈希函数选模数时，尽量取质数。一个经典原因是：如果取合数，某些数据分布下模运算后哈希值的分布不均匀，会集中到少数槽位，冲突率飙升。
比如取 N=10000，数据全是一堆10的倍数，那么哈希值全是0，所有元素挤在同一个桶里，哈希表退化成链表，复杂度直接变O(n^2)。
取质数能打散这种规律性。这也是写哈希表时的常见坑：不要图省事随便选个看起来很大的数，先确认它是不是质数。
N=2000003 就是质数，整体表现稳定。
5. 常见编程陷阱
5.1 多组测试数据的初始化
题目有时候是多组输入，每个测试点内部有一个n，但测试点之间要重新初始化哈希表。
我最开始学的时候犯过错：只初始化一次，结果第二组测试数据直接查到了上一组留下的老值，导致所有数都被判为“重复”，输出为空。这个问题很隐蔽，因为样例可能只有一组数据，一跑就过，提交就错。
解决办法：在主循环里，每次进入新的测试组之前，把数组重置成EMPTY。如果有多个测试组，注意memset的用法。memset(h, 0xff, sizeof(h))会把每个字节设为0xff，也就是整个int变成-1，如果EMPTY正好是-1就能直接用。
5.2 行末空格
很多OJ严格比对输出，行尾多了空格会判Presentation Error，甚至Wrong Answer。所以我在输出的时候用一个first变量标记是否该输出空格。
5.3 输入输出效率
用std::cin和std::cout时，如果题目数据量上百万，可能因为同步原因很慢。
在竞赛中建议加一行：
std::ios::sync_with_stdio(false); std::cin.tie(nullptr);或者直接用scanf和printf。实测下来，在数据量百万级时这行代码能显著减少IO耗时。
5.4 哈希表删除问题
这道题不需要删除操作，所以开放寻址法顺风顺水。但如果你以后遇到“删除元素”的需求，要注意开放寻址法删除比较麻烦，得用特殊标记“已删除”，而不是直接清空成空。否则会导致后续查询路径断裂，明明有元素却查不到。
6. 离散化也是一种可行方案
6.1 什么是离散化
离散化就是把值域很大的数据，映射到一个紧凑的区间上。做法是：把所有出现的数先收集起来，排序去重，然后给每个不同的数分配一个从0开始的编号。之后判断是否出现过，只需要看“编号”是否出现过即可。
举个生活化例子：班级里学生姓名各不相同，老师为了方便，给他们编学号01、02、03。后续点名直接按学号点，不用反复喊全名。
6.2 具体流程
- 读入所有数据，存到数组
a中 - 复制一份数组
b = a，对b排序 - 对
b去重，得到有序的唯一值列表 - 用二分查找把
a中每个数映射到下标 - 开一个普通的
bool vis[]，长度为唯一值个数 - 遍历原数组，如果该下标的vis为false，输出该数并置为true
缺点是需要两趟遍历且必须先存下所有数据，不能在线处理。优点是代码稳定、不用考虑哈希冲突。数据量百万以下时，离散化完全可行。
6.3 离散化模板块
#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> a, b; int x; while (std::cin >> x) { a.push_back(x); } b = a; std::sort(b.begin(), b.end()); b.erase(std::unique(b.begin(), b.end()), b.end()); std::vector<bool> vis(b.size(), false); bool first = true; for (int v : a) { int idx = std::lower_bound(b.begin(), b.end(), v) - b.begin(); if (!vis[idx]) { if (!first) std::cout << ' '; std::cout << v; first = false; vis[idx] = true; } } std::cout << '\n'; return 0; }这里的核心是std::lower_bound，它返回第一个不小于v的位置。因为v一定在b里，所以返回的位置就是它的唯一编号。
时间复杂度：排序 O(n log n)，二分查找 O(n log n)，总复杂度比哈希略高，但常数小、代码稳健。
7. 实测与选择建议
7.1 三种方案对比
| 方案 | 时间复杂度 | 空间复杂度 | 代码难度 | 适用场景 |
|---|---|---|---|---|
| 暴力遍历 | O(n^2) | O(n) | 极低 | 只适合n≤1000 |
| unordered_set | O(n)平均 | O(n) | 低 | 绝大多数题目 |
| 手写哈希表 | O(n)平均 | O(N) | 中 | 卡常、特殊环境 |
| 离散化 | O(n log n) | O(n) | 中 | 需要稳定、避免冲突 |
如果你用的是AcWing平台，unordered_set一般能过，但为了练习底层原理，我还是推荐至少写一遍手写哈希表。
如果你在打比赛时实在时间不够，直接用unordered_set省心。但要注意把reserve和max_load_factor设置好：
std::unordered_set<int> seen; seen.reserve(2000000); seen.max_load_factor(0.7);reserve能提前分配空间，避免多次扩容。max_load_factor(0.7)表示装载因子超过0.7就扩容，减少冲突。实测上百万数据时，这两行设置能明显提升速度。
7.2 数据规模经验
- n ≤ 1000：暴力也能过，但没必要
- n ≤ 10^5：
unordered_set随便写，基本都过 - n ≤ 10^6：注意IO优化，用手写哈希更稳
- n ≤ 10^7：哈希表N要开很大，内存可能吃紧，建议考虑其他算法
这道题如果n到了10^6级别，cout加endl会非常致命，endl会刷新缓冲区，一次刷新就是一次系统调用。记住：不要用endl，用\n。
8. 如何把这道题经验迁移到其他题目
8.1 判断唯一性
“判断一个数是否出现过”是很多题的基础子问题。比如：
- 字符串去重：把字符串转为哈希值再判断
- 判断数组中是否存在两数之和等于目标值：边遍历边存哈希，只需要O(n)
- 最长连续序列：先全部入哈希，再逐个扩展
- 单词出现次数：用
unordered_map统计频率
这题之后，你再去写这类题会非常有底，因为你已经知道“去重”不是题目核心，“高效查询”才是。
8.2 从哈希表到更多结构
手写哈希理解后，你可以继续向几个方向深入：
- 字符串哈希，也就是BKDR或者双哈希
- 哈希加链表做LRU缓存
- 布隆过滤器，用于大量数据的存在性判断
每一条都会用到“哈希”这个基础概念，但应用层次完全不同。我们做个总结：AcWing 2951 是个小题目，但它的价值不小。它能检验一个人是否真的理解哈希表的用途，而不是只会背模板。做题时多想想“为什么数组不行”“为什么用质数”“为什么冲突要线性探测”，比刷十道重复题更有收获。
我自己刚开始做这道题时，第一版写的是unordered_set，过了；但我总感觉差点意思。后来手写了一遍哈希表，把负数和多组输入两个坑都踩了一遍，才算真正通透了。所以建议你也别偷懒，标准库写一遍，手写一遍，再写一遍离散化版本。三种方法全过一遍以后，再遇到“去重”类题目，基本就是降维打击。
