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压缩一下一个bitset1000000000也只占用约125MB依然可能超出限制。而且题目还可能出现负数和超大正数数组下标的天然限制让这条路彻底走不通。2.2 用普通数组现炒现卖不行还有同学说那我用一个普通数组每读到一个数就遍历一遍已经保存的数组看有没有出现过没有就加进去。这样空间不炸时间炸了。假设总共n个数每个数都不同那么第i个数需要和前面i-1个数比较总比较次数大约是123...(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那么 x7 和 x14 都会落到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_setint 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 为什么值得手写不写标准库反而要手写哈希表有以下几个原因有些题目环境不支持C11unordered_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要取质数哈希函数选模数时尽量取质数。一个经典原因是如果取合数某些数据分布下模运算后哈希值的分布不均匀会集中到少数槽位冲突率飙升。比如取 N10000数据全是一堆10的倍数那么哈希值全是0所有元素挤在同一个桶里哈希表退化成链表复杂度直接变O(n^2)。取质数能打散这种规律性。这也是写哈希表时的常见坑不要图省事随便选个看起来很大的数先确认它是不是质数。N2000003 就是质数整体表现稳定。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::vectorint 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::vectorbool 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≤1000unordered_setO(n)平均O(n)低绝大多数题目手写哈希表O(n)平均O(N)中卡常、特殊环境离散化O(n log n)O(n)中需要稳定、避免冲突如果你用的是AcWing平台unordered_set一般能过但为了练习底层原理我还是推荐至少写一遍手写哈希表。如果你在打比赛时实在时间不够直接用unordered_set省心。但要注意把reserve和max_load_factor设置好std::unordered_setint seen; seen.reserve(2000000); seen.max_load_factor(0.7);reserve能提前分配空间避免多次扩容。max_load_factor(0.7)表示装载因子超过0.7就扩容减少冲突。实测上百万数据时这两行设置能明显提升速度。7.2 数据规模经验n ≤ 1000暴力也能过但没必要n ≤ 10^5unordered_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过了但我总感觉差点意思。后来手写了一遍哈希表把负数和多组输入两个坑都踩了一遍才算真正通透了。所以建议你也别偷懒标准库写一遍手写一遍再写一遍离散化版本。三种方法全过一遍以后再遇到“去重”类题目基本就是降维打击。