先问一个问题你刷算法题的时候是不是总觉得“暴力解法”四个字带着点贬义好像提暴力解就低人一等我当年准备面试的时候也这么觉得。直到后来真上了考场被一道“简单题”问得满头大汗才明白一个道理——暴力不是原罪只会暴力才是。面试官想看的从来不是“你直接背出了最优解”而是你怎么从一个最朴素的思路出发一步步想清楚复杂度瓶颈在哪、优化空间在哪、边界条件怎么处理。LeetCode上的“存在重复元素”217题就是这种题里最典型的一道。题面短到不能再短给你一个整数数组判断是否存在两个相同的元素。看着人畜无害但它能在面试里同时考察你的编码功底、复杂度分析、对哈希表底层机制的理解甚至追问出两三道变种题。这篇文章我就把这题从暴力到优雅的所有走法都掰开揉碎讲一遍包括我面别人和被人面时候的真实体会。看完你会发现“剑斩OFFER”靠的从来不是那道最优解而是你推导出最优解的那条路。1. 题面背后的考点为什么“存在重复元素”能拦住一堆候选人先说结论这题能拦住人不是因为难是因为太简单了简单到很多人懒得认真对待。但就是这种“简单题”最容易暴露一个人的基本功。1.1 题目到底在问什么原题描述大概是这样的给你一个整数数组nums。如果任一值在数组中出现至少两次返回true如果数组中每个元素互不相同返回false。没了就这些。示例不贴了脑子里能想到的数组都能跑。但这道题真正考的东西写在不言处能不能读懂题目背后的集合论语义重复元素 集合大小小于数组大小这是抽象能力。能不能快速排出可行的解法空间暴力双重循环、排序、哈希复杂度从 O(n²) 到 O(n log n) 到 O(n)你是否心里有数。能不能写出健壮的代码空数组、单元素数组、负数、超大值每个边界你都考虑到了吗循环里能不能别写nums[i] nums[j]然后break完事不管。能不能应对面试官的追问如果数组特别大内存装不下哈希表怎么办如果元素范围有限怎么办如果要求返回重复的那个元素呢这些都是“存在重复元素”这道题表面之下真正值钱的东西。所以别嫌它简单把它当成一面镜子——你能在这道题上答出多少层次基本反映了你算法基础的上限。1.2 大多数人最容易踩的两个坑我面过不少候选人这道题上最常见的错误有两个。第一个一上来就写哈希表但完全说不清楚哈希表为什么快。你问他“如果我用set可不可以”他说“可以”你问他“set和unordered_set谁快”他愣住。这说明他是背的答案不是真的理解。在实际工程里这种“背题式选手”最危险——换个马甲的问法立刻就露馅。第二个循环边界写错。很多人写双重循环判断重复内层循环从j 0开始于是i j的时候必然相等直接返回true。这种代码一跑示例就报错属于典型的“没在纸上跑过”。这俩坑都不高级但架不住年年有人踩。说明什么说明很多人刷题是真在“刷”不是在“理解”。2. 暴力解法还原现场先把最笨的路走通再谈优化我相信所有人在第一次遇到这道题的时候脑子里冒出来的第一个解法都是同一个——两层循环逐个比较。bool containsDuplicate(vectorint nums) { int n nums.size(); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (nums[i] nums[j]) { return true; } } } return false; }这段代码的思路直接到不能再直接每拿一个元素跟它后面的所有元素比一遍。只要发现相等的就说明有重复全部比完都没发现就说明没有重复。2.1 为什么说这是“暴力美学”的起点别急着嘲笑这个解法。暴力解法的价值不在于它快而在于它永远正确。不管数据长什么样它都能给出正确答案——这就是它的“美学”所在简单、直观、不可能出错。就像你要找一堆苹果里有没有两个一样大的。最笨的办法当然是一个个比过去但这办法它不会漏对不对算法的第一要义是正确性不是漂亮。你先保证自己对题目的理解是正确的再谈怎么跑得快。从工程角度讲暴力解是验证最优解正确性的基准。我实际开发的时候偶尔需要写个算法第一版一定是最容易读懂的版本先保证功能对再去看 profiling 结果决定优化哪里。一上来就“优化”往往是过早优化浪费大量时间。2.2 暴力解的时间账本双重循环最坏情况下数组里完全没有重复元素你得比较多少次第一次外层循环内层跑n-1次第二次外层n-2次依此类推。总次数是(n-1) (n-2) ... 1 n * (n-1) / 2 ≈ n²/2所以时间复杂度是O(n²)空间复杂度是O(1)——除了几个循环变量额外啥都没用。这个复杂度意味着什么如果数组有 10000 个元素最坏情况下要跑约 5000 万次比较如果数组有 1000000 个元素那就是约 5000 亿次。你可以在脑子里感受一下“从 5000 万到 5000 亿”这个量级的跳跃——这就是为什么暴力解只能作为思路起点不能作为面试终点。2.3 暴力解里的工程细节怎么把常数因子压一压暴力解虽然是 O(n²)但常数因子还是有优化空间的。我面试的时候有时候会追问“假设我就让你写暴力解你能怎么让它稍微快点”几个实操层面的点内层循环从i1开始避免自己跟自己比这是基础。把nums.size()提前存到n里不要每次循环都调用函数尤其是在for (int j i 1; j n; j)这种写法里size()是 O(1) 的但函数调用开销能省则省。尽早 return。一旦发现重复立刻返回不要继续跑。这个在平均情况数据分布均匀时能省很多时间。考虑访问顺序。nums[i]在外层已经固定内层反复读这个值可以先存成局部变量int x nums[i]减少内存访问次数。编译器大概率会优化但你自己写出来至少说明你懂局部性原理。当然这些都是“术”的层面面试官不会因为你常数优化而给你加分太多。但如果你能把“为什么暴力解慢”的本质——比较次数随n的增长呈平方级增长——讲得清清楚楚反而能加分。3. 排序解法用 O(n log n) 换掉 O(n²) 的那笔划算买卖暴力解最大的问题是什么重复比较。你比较了nums[0]和nums[3]又比较nums[1]和nums[3]这些比较互相之间完全没利用上。那有没有办法让比较“有记忆”有。先排序然后只需要检查相邻元素是否相等。bool containsDuplicate(vectorint nums) { sort(nums.begin(), nums.end()); for (int i 1; i nums.size(); i) { if (nums[i] nums[i - 1]) { return true; } } return false; }为什么排序之后只需要看邻居因为排序会把相同的元素聚到一起。如果数组里有重复元素排完序后它们必然挨在一起。所以从头扫到尾每次只看当前元素和前一个是否相等就够了。3.1 这个解法怎么想到的很多初学者拿到题只会想到“比较”想不到“排序”。这其实是个数学上的思维转换原来判断“是否存在相等对”是元素和元素之间的 pairwise 比较复杂度天然就是 O(n²)但排序相当于给数组建立了“序”的结构把“相等关系”变成了“相邻关系”从无从下手变成了线性扫描。我说句实话刷题刷到一定量之后看到“存在性判断”的题第一反应就应该是能不能先排序。排序这个操作本身很贵O(n log n)但它能把后面的问题从 O(n²) 降到 O(n)。这笔买卖只要 n 稍微大一点都是赚的。算个账假设 n 10000。暴力解要跑约 5000 万次比较排序解法排序约 13 万次比较扫描 1 万次加起来不到 15 万次。差了 300 多倍。这就是算法的魅力——不是机器变快了是你在同样的机器上做了更少的事。3.2 排序解法的注意事项这个解法看似简单细节里全是坑。第一个坑排序会改变原数组。如果你在其他语言里用的是传引用C 默认sort就是原地排那么调用完containsDuplicate外部传进的数组就已经被改了。很多实际场景里你只是“检查一下”并不希望数据被重排。有两种应对一是在函数内拷贝一份再排序代价是额外 O(n) 空间二是事先明确这个函数的副作用在注释里写清楚“会修改输入数组”。面试的时候我建议主动提一句“这个解法会改变原数组如果面试要求不能修改原数组我需要先拷贝一份”这会让面试官觉得你有工程意识。第二个坑C 的std::sort是不稳定排序。这道题对稳定性没有要求因为相等元素是否保持相对顺序完全不影响“是否存在重复”这个判断。但如果你在别的题里用“先按 A 排序、再按 B 排序”的技巧必须注意std::stable_sort才是稳定排序。这是很多人在其他题目上翻车的经典原因在这道题里倒是无关紧要。第三个坑面试官会追问“排序为什么是 O(n log n)”。很多人背过sort的复杂度但被问到底层算法是什么就懵。标准库的sort通常是内省排序IntroSort——一种结合了快速排序、堆排序和插入排序的混合算法最坏情况也是 O(n log n)。你能把这个讲明白面试官的眼神会变。3.3 排序解法的隐藏优势哈希表解法空间 O(n)排序解法空间 O(1)原地排序的话。如果面试官说“我希望空间复杂度尽可能低数组可以被修改”那排序解法就是最优解。这个伏笔在后面“追问”环节会很有用。另外排序解法其实给后续变种题打了个底。比如“找出数组中第一个重复出现的元素”“找出出现次数最多的元素”排序之后都变成了线性扫描问题。排序是一种通用预处理它解决的不止一道题而是一类题。4. 哈希表才是这题的标准答案空间换时间的经典权衡终于说到面试中最常被期望说出的解法了。思路很简单遍历数组把每个元素放进一个集合里。如果放的过程中发现“这个元素已经在集合里了”就说明有重复。bool containsDuplicate(vectorint nums) { unordered_setint seen; for (int num : nums) { if (seen.count(num)) { return true; } seen.insert(num); } return false; }一次遍历每个元素的插入和查找在平均情况下都是 O(1)所以整体时间复杂度O(n)空间复杂度O(n)。4.1 为什么是unordered_set而不是set这个点值得展开说因为太多人栽在这上面了。C 标准库里有两个容器可以“存不重复元素”std::set和std::unordered_set。std::set的底层是红黑树一种自平衡二叉查找树插入、查找、删除都是 O(log n)。好处是有序可以快速找前驱后继、范围查询。std::unordered_set的底层是哈希表插入、查找在平均情况下是 O(1)。坏处是无序而且最坏情况下哈希冲突严重会退化到 O(n)。在这道题里我们只需要“判断存在性”完全不需要“有序”这个特性所以unordered_set是明显更合理的选择。如果你的代码里用了set面试官很可能会追问“为什么不用unordered_set”——你要是答不上来分数直接扣一截。反过来如果面试官问“能不能用multiset”答案是可以但没必要。multiset允许重复元素判断是否有重复可以插入后看count 1但这个容器比set更重语义也不直接属于“能用但不是最优设计”。4.2 哈希表背后的原理拉链法与负载因子面试官如果继续深入通常会问哈希表本身。哈希表把元素通过哈希函数映射到一个数组下标桶上。不同的元素可能映射到同一个桶这就是哈希冲突。最常见的解决方式是链地址法拉链法每个桶背后挂一个链表或红黑树冲突的元素都放在这个桶的链表里。当链表过长时查找效率就会下降。所以哈希表有一个负载因子元素个数 / 桶个数的概念超过阈值C 标准库通常默认 1.0就rehash——也就是扩容重新分配桶重新计算所有元素的哈希位置。这就是为什么unordered_set的平均操作是 O(1)但最坏情况是 O(n)如果哈希函数设计得极差所有元素都映射到同一个桶那哈希表就退化成一个链表查找就是线性扫描。有个工程细节如果你提前知道数据量很大可以reserve预留空间减少 rehash 带来的开销。unordered_setint seen; seen.reserve(nums.size());这一行代码在小数据量下无所谓但如果nums有上百万个元素能显著减少扩容带来的性能损耗。面试时写这一行绝对是加分项——它说明你了解哈希表的行为而不只是会用 API。4.3 早期返回的收益与陷阱哈希表解法还有一个容易被忽略的工程点如果重复出现得很早能不能提前退出能。上面代码里一发现count为真就return true这就是提前退出。最好情况下前两个元素就重复跑两次循环就完事。但这里有个陷阱如果你把“全部插入完再统一判断”写成两遍循环比如先全部insert然后再遍历一遍数count那一个 O(n) 的操作就变成了 2n虽然复杂度还是 O(n)但常数因子翻倍了。更重要的是当你用哈希表做存在性判断时一边插入一边检查几乎是唯一正确的姿势——你想想如果重复的元素在数组前面你全部插完再查岂不是白跑一趟这个“边插边查”的模式在很多哈希表相关的题目里都会出现比如“两数之和”“最长连续序列”都是一样的套路。其实这就是一个通用模板遍历每个元素 如果当前元素在集合里找到重复返回 否则把当前元素加入集合可以说这道题不只是考你知不知道哈希表更是考你知不知道哈希表在存在性判断里的标准用法。5. 不那么常见但偶尔有奇效的思路鸽巢原理与位图法前面的解法都是“通用武器”。但面试官如果觉得前面几关你都轻松过了可能会给一个看起来像是“增加难度”的前提限制这时候就需要一点不那么通用的武器。5.1 鸽巢原理能不能在遍历之前就“截胡”鸽巢原理也叫抽屉原理说得很直白如果你有n 1只鸽子要放进n个鸽巢那至少有一个巢里有两只鸽子。套到这道题里如果数组的每个元素都被限制在区间[0, n-1]之间而数组长度也是n那么只有两种情况——要么所有元素正好是0到n-1各出现一次要么必然有重复。这题目常出现的变体版本就是给定的数组长度为 n元素取值在 [0, n-1] 范围内请判断是否有重复元素。有了这个限制条件一个很妙的做法就出来了把每个元素放到它“应该在”的位置上。元素x应该放到下标x的位置。如果发现目标位置已经放着正确的元素那就有重复了。bool containsDuplicate(vectorint nums) { int n nums.size(); for (int i 0; i n; i) { while (nums[i] ! i) { if (nums[nums[i]] nums[i]) { return true; } swap(nums[i], nums[nums[i]]); } } return false; }这个解法的时间复杂度是 O(n)每个元素最多被交换两次空间复杂度是 O(1)而且不需要额外哈希表。它的本质是把数组本身当作哈希表来用——元素值就是它的哈希位置。面试时能写出这个解法基本等于告诉面试官你不仅会背哈希表还理解哈希表的本质是“位置映射”。但注意这个解法有一个重要前提元素值必须在[0, n-1]范围内。如果超出这个范围就得先做偏移或者映射。面试中如果题目给了这个限制这个解法几乎是最优的——时间 O(n)、空间 O(1)、无副作用。5.2 位图法当内存吃紧的时候怎么办回到通用版本如果面试官说“数据量非常大比如几亿个整数内存放不下一个完整的unordered_set你怎么办”一个经典思路是位图bitmap。假设你知道元素的值域范围比如所有整数都在[0, 10^9]之间你可以开一个对应大小的位数组每个位表示“这个值是否出现过”。遍历数组如果对应位已经是 1说明重复否则置为 1。位图相对于哈希表的优势是极低的常数空间一个位只占 1 bit。比如要标记 1 亿个可能的整数只需要约 12 MB 内存而存 1 亿个int的unordered_set轻松超过 1 GB。C 里可以用std::vectorbool——虽然这个东西在设计上有争议但当作位图用是完全可以的。也可以用bitset但bitset要求编译期确定大小不适合运行时才知道值域范围的场景。bool containsDuplicate(vectorint nums, int valueRange) { vectorbool bitmap(valueRange 1, false); for (int num : nums) { if (bitmap[num]) { return true; } bitmap[num] true; } return false; }时间复杂度依然是 O(n)空间取决于值域范围而不是元素个数。不过这个解法有个明显前提值域不能太大而且不能有负数或者说负值需要做偏移。如果值域是[-10^9, 10^9]你需要 2×10^9 个 bit约 250 MB 内存——倒不是不可接受但便宜占得就有限了。所以实际面试中位图解法更多是作为一个“思考方向”被提及而不是首选。5.3 这些“歪招”的真正价值说实话这题你面试时用不着把鸽巢原理和位图法全部写出来。但这些思路的存在证明了同一个问题可以有不同的切入角度暴力从定义出发比较所有元素对排序从结构出发利用序关系简化判断哈希从记忆出发用空间换时间鸽巢从数学出发利用值域信息提前剪枝位图从工程出发针对大数据量压缩存储每个角度都有自己的适用场景。“暴力美学”这四个字说的不是某一种解法而是这种不断换个角度看同一个问题的过程本身——它是有美感的。6. 面试官视角这道题怎么答才算“剑斩OFFER”最后聊聊实战。我面别人也好帮朋友模拟面试也好这道题出现的频率相当高因为它太适合用来区分“背题的”和“真会的”。6.1 面试中推荐的作答路径不要一上来就甩哈希表。我建议的答题节奏是第一步确认题意。复述一遍“我要判断数组里是否有任一元素出现至少两次返回布尔值。”如果有必要问清楚数组长度范围、元素值域、是否允许修改原数组。这步很基础却能让面试官看到你的沟通习惯。第二步先给暴力解。简单说一句“最简单的方法是两两比较时间复杂度 O(n²)空间 O(1)”并快速写出代码或伪代码。这不是浪费时间——它向面试官证明你的思考是从正确性出发而不是从背诵出发。第三步自己指出问题。“这个解法在 n 很大时过不了我们来优化。”然后给出排序思路“可以先排序再检查相邻元素时间复杂度降到 O(n log n)空间 O(1)。但它的前提是可以修改原数组。”第四步再进一步到哈希表“用unordered_set一边遍历一边查平均 O(n) 时间O(n) 空间。这是这道题理论上的最优时间。”写出完整代码。第五步补充边界条件。“空数组、单元素数组、负数、重复元素在开头和结尾的情况这个实现都能正确处理。另外如果要保留原数组我会先拷贝一份再排序。”这一套下来面试官看到的不是“一个人背了一道题”而是一个有分析路径、有复杂度意识、有工程判断力的候选人。这才是“剑斩OFFER”的真正含义——你不是靠记住答案打败对手而是靠展示思维方式碾压对手。6.2 常见的追问与应对面试官在收到哈希表答案后很可能追问如下几个问题“如果不能用额外空间怎么做”答排序。sort后检查相邻元素原地排 O(1) 空间。前提是允许修改数组。“如果不允许修改原数组呢”答那只能哈希表或者拷贝一份再排序。到这里面试官其实就在引导你比较时间-空间的 trade-off。“如果数据特别大内存放不下哈希表怎么办”答可以考虑位图如果值域可控或者分布式思路、外部排序——看你假设的场景。对这道题而言提位图就够了分布式一般不会在这里展开。“如果要求返回第一个重复的元素呢”答哈希表天然适合遍历时第一次发现“已在集合中”的那个元素就是第一个重复的。排序解法就看不出这个了。“如果重复元素可能有很多个找出现次数最多的元素呢”答哈希表统计频次遍历一遍找最大值。这个扩展就自然转移到了“数组中的众数”这类题。每一个追问本质上都在测试你对数据结构特性的理解有多深。你能接住追问这道题才算真正答完。6.3 关于“暴力美学”我的真实理解回到标题里的四个字——“暴力美学”。很多人以为这四个字说的是暴力解法本身很美。但真刷过题、真面过试的人应该明白暴力解法的美不在于它快而在于它定义了一个起点。所有优化都是你从起点出发一步步发现“这里有冗余”“这里可以用空间换时间”“这里可以借用数学性质”最终走到一个优雅解的过程。没有暴力解你连起点都没有。所以我特别鼓励准备面试的人拿到一道题先别急着回忆“我是不是刷过这道题”。先老老实实想最笨的办法然后从最笨的办法出发问自己三个问题慢在哪找瓶颈有没有办法消掉这些瓶颈换数据结构 or 换算法这些优化牺牲了什么空间稳定性原数组你把这三个问题走完这道题就算彻底吃透了。“存在重复元素”这种简单题都吃透了后面那些复杂题无非是把这套思维用得更复杂一点而已。7. 变种题与延伸一道题打通一个系列说点实际的——面试官出“存在重复元素”的时候往往不会只考这一道。他手里还有两个经典变种随时准备顺着你的答案继续往外掏。7.1 变种一存在重复元素 II219 题题面也简单给定数组问是否存在两个相等的元素并且它们的下标的差的绝对值不超过 k。这题的暴力解法就是双重循环加一个下标差判断但最优解是在哈希表基础上加个滑动窗口的思想遍历数组维护一个大小为 k 的窗口。每次只看窗口内有没有当前元素。窗口可以用unordered_set模拟每次遍历到新元素先查 set有就返回 true然后插入当前元素如果 set 大小超过 k就删掉最早加入的那个元素。bool containsNearbyDuplicate(vectorint nums, int k) { unordered_setint window; for (int i 0; i nums.size(); i) { if (window.count(nums[i])) { return true; } window.insert(nums[i]); if (window.size() k) { window.erase(nums[i - k]); } } return false; }这题考的是有界窗口和“如何删除过期数据”。很多人在erase(nums[i - k])这一步卡壳——这里的本质是每次窗口移动一格就要把窗口最左边的元素踢出去。你要是能答出来面试官基本确认你的哈希表不是白刷的。7.2 变种二存在重复元素 III220 题这题难度直接拉满给定数组问是否存在两个元素它们的值差的绝对值不超过 t且下标差的绝对值不超过 k。这题最优雅的解法是桶排序思想把每个元素按值分桶桶的大小设为 t1。如果两个元素被分到同一个桶那它们的值差一定不超过 t如果相邻桶还需要再比较一下。这题用unordered_map实现桶即可。bool containsNearbyAlmostDuplicate(vectorint nums, int k, int t) { unordered_maplong, long buckets; long bucketSize (long)t 1; for (int i 0; i nums.size(); i) { long num nums[i]; long bucketId (num - INT_MIN) / bucketSize; if (buckets.count(bucketId)) return true; if (buckets.count(bucketId - 1) abs(num - buckets[bucketId - 1]) t) return true; if (buckets.count(bucketId 1) abs(num - buckets[bucketId 1]) t) return true; buckets[bucketId] num; if (i k) { long oldBucketId ((long)nums[i - k] - INT_MIN) / bucketSize; buckets.erase(oldBucketId); } } return false; }这个解法里面最值得琢磨的是“按值分桶”的思想——它把一个“差值限制”问题转化成了“同桶或邻桶”问题。当你从“存在重复元素”一路走到这里回头看你会发现这套题其实在讲一件事如何根据不同的约束条件设计不同的查找结构。7.3 刷题策略把一道题当成一个系列来学我见过很多刷题的人按题号一题一题往后做做完 217 就看 218做到 219 发现“哦这题跟 217 不一样”然后又从零开始想。这样的效率其实很低。更好的做法是按主题、按系列刷。拿到“存在重复元素 I”就主动把 II 和 III 也做了。这样你不仅掌握了一道题你还掌握了一类问题的演化路径。面试的时候面试官从 217 追问到 219再到 220你不是“遇到新题”而是“复习旧知识”——心态完全不一样。这也是我在这篇文章最后最想强调的一点暴力美学的终点是你在各种解法之间自由切换、游刃有余的状态。到了那个状态任何一道面试题不管是简单的还是复杂的都只是你思维路径上的一个普通节点而已。我在实际面试别人时最怕的不是候选人不会做难题而是候选人只会背答案。会背哈希表的答案、会写出unordered_set的代码不等于理解哈希表为什么能解决这个问题。你试试在“存在重复元素”这道题上把每个解法的时间复杂度、空间复杂度、适用前提都能讲清楚把面试官的问题从暴力问到哈希、从哈希问到鸽巢原理、从鸽巢原理问到变种题——你就知道什么叫“一剑斩落OFFER”了。 从暴力到哈希：LeetCode 217存在重复元素的五种解法与面试技巧
先问一个问题你刷算法题的时候是不是总觉得“暴力解法”四个字带着点贬义好像提暴力解就低人一等我当年准备面试的时候也这么觉得。直到后来真上了考场被一道“简单题”问得满头大汗才明白一个道理——暴力不是原罪只会暴力才是。面试官想看的从来不是“你直接背出了最优解”而是你怎么从一个最朴素的思路出发一步步想清楚复杂度瓶颈在哪、优化空间在哪、边界条件怎么处理。LeetCode上的“存在重复元素”217题就是这种题里最典型的一道。题面短到不能再短给你一个整数数组判断是否存在两个相同的元素。看着人畜无害但它能在面试里同时考察你的编码功底、复杂度分析、对哈希表底层机制的理解甚至追问出两三道变种题。这篇文章我就把这题从暴力到优雅的所有走法都掰开揉碎讲一遍包括我面别人和被人面时候的真实体会。看完你会发现“剑斩OFFER”靠的从来不是那道最优解而是你推导出最优解的那条路。1. 题面背后的考点为什么“存在重复元素”能拦住一堆候选人先说结论这题能拦住人不是因为难是因为太简单了简单到很多人懒得认真对待。但就是这种“简单题”最容易暴露一个人的基本功。1.1 题目到底在问什么原题描述大概是这样的给你一个整数数组nums。如果任一值在数组中出现至少两次返回true如果数组中每个元素互不相同返回false。没了就这些。示例不贴了脑子里能想到的数组都能跑。但这道题真正考的东西写在不言处能不能读懂题目背后的集合论语义重复元素 集合大小小于数组大小这是抽象能力。能不能快速排出可行的解法空间暴力双重循环、排序、哈希复杂度从 O(n²) 到 O(n log n) 到 O(n)你是否心里有数。能不能写出健壮的代码空数组、单元素数组、负数、超大值每个边界你都考虑到了吗循环里能不能别写nums[i] nums[j]然后break完事不管。能不能应对面试官的追问如果数组特别大内存装不下哈希表怎么办如果元素范围有限怎么办如果要求返回重复的那个元素呢这些都是“存在重复元素”这道题表面之下真正值钱的东西。所以别嫌它简单把它当成一面镜子——你能在这道题上答出多少层次基本反映了你算法基础的上限。1.2 大多数人最容易踩的两个坑我面过不少候选人这道题上最常见的错误有两个。第一个一上来就写哈希表但完全说不清楚哈希表为什么快。你问他“如果我用set可不可以”他说“可以”你问他“set和unordered_set谁快”他愣住。这说明他是背的答案不是真的理解。在实际工程里这种“背题式选手”最危险——换个马甲的问法立刻就露馅。第二个循环边界写错。很多人写双重循环判断重复内层循环从j 0开始于是i j的时候必然相等直接返回true。这种代码一跑示例就报错属于典型的“没在纸上跑过”。这俩坑都不高级但架不住年年有人踩。说明什么说明很多人刷题是真在“刷”不是在“理解”。2. 暴力解法还原现场先把最笨的路走通再谈优化我相信所有人在第一次遇到这道题的时候脑子里冒出来的第一个解法都是同一个——两层循环逐个比较。bool containsDuplicate(vectorint nums) { int n nums.size(); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (nums[i] nums[j]) { return true; } } } return false; }这段代码的思路直接到不能再直接每拿一个元素跟它后面的所有元素比一遍。只要发现相等的就说明有重复全部比完都没发现就说明没有重复。2.1 为什么说这是“暴力美学”的起点别急着嘲笑这个解法。暴力解法的价值不在于它快而在于它永远正确。不管数据长什么样它都能给出正确答案——这就是它的“美学”所在简单、直观、不可能出错。就像你要找一堆苹果里有没有两个一样大的。最笨的办法当然是一个个比过去但这办法它不会漏对不对算法的第一要义是正确性不是漂亮。你先保证自己对题目的理解是正确的再谈怎么跑得快。从工程角度讲暴力解是验证最优解正确性的基准。我实际开发的时候偶尔需要写个算法第一版一定是最容易读懂的版本先保证功能对再去看 profiling 结果决定优化哪里。一上来就“优化”往往是过早优化浪费大量时间。2.2 暴力解的时间账本双重循环最坏情况下数组里完全没有重复元素你得比较多少次第一次外层循环内层跑n-1次第二次外层n-2次依此类推。总次数是(n-1) (n-2) ... 1 n * (n-1) / 2 ≈ n²/2所以时间复杂度是O(n²)空间复杂度是O(1)——除了几个循环变量额外啥都没用。这个复杂度意味着什么如果数组有 10000 个元素最坏情况下要跑约 5000 万次比较如果数组有 1000000 个元素那就是约 5000 亿次。你可以在脑子里感受一下“从 5000 万到 5000 亿”这个量级的跳跃——这就是为什么暴力解只能作为思路起点不能作为面试终点。2.3 暴力解里的工程细节怎么把常数因子压一压暴力解虽然是 O(n²)但常数因子还是有优化空间的。我面试的时候有时候会追问“假设我就让你写暴力解你能怎么让它稍微快点”几个实操层面的点内层循环从i1开始避免自己跟自己比这是基础。把nums.size()提前存到n里不要每次循环都调用函数尤其是在for (int j i 1; j n; j)这种写法里size()是 O(1) 的但函数调用开销能省则省。尽早 return。一旦发现重复立刻返回不要继续跑。这个在平均情况数据分布均匀时能省很多时间。考虑访问顺序。nums[i]在外层已经固定内层反复读这个值可以先存成局部变量int x nums[i]减少内存访问次数。编译器大概率会优化但你自己写出来至少说明你懂局部性原理。当然这些都是“术”的层面面试官不会因为你常数优化而给你加分太多。但如果你能把“为什么暴力解慢”的本质——比较次数随n的增长呈平方级增长——讲得清清楚楚反而能加分。3. 排序解法用 O(n log n) 换掉 O(n²) 的那笔划算买卖暴力解最大的问题是什么重复比较。你比较了nums[0]和nums[3]又比较nums[1]和nums[3]这些比较互相之间完全没利用上。那有没有办法让比较“有记忆”有。先排序然后只需要检查相邻元素是否相等。bool containsDuplicate(vectorint nums) { sort(nums.begin(), nums.end()); for (int i 1; i nums.size(); i) { if (nums[i] nums[i - 1]) { return true; } } return false; }为什么排序之后只需要看邻居因为排序会把相同的元素聚到一起。如果数组里有重复元素排完序后它们必然挨在一起。所以从头扫到尾每次只看当前元素和前一个是否相等就够了。3.1 这个解法怎么想到的很多初学者拿到题只会想到“比较”想不到“排序”。这其实是个数学上的思维转换原来判断“是否存在相等对”是元素和元素之间的 pairwise 比较复杂度天然就是 O(n²)但排序相当于给数组建立了“序”的结构把“相等关系”变成了“相邻关系”从无从下手变成了线性扫描。我说句实话刷题刷到一定量之后看到“存在性判断”的题第一反应就应该是能不能先排序。排序这个操作本身很贵O(n log n)但它能把后面的问题从 O(n²) 降到 O(n)。这笔买卖只要 n 稍微大一点都是赚的。算个账假设 n 10000。暴力解要跑约 5000 万次比较排序解法排序约 13 万次比较扫描 1 万次加起来不到 15 万次。差了 300 多倍。这就是算法的魅力——不是机器变快了是你在同样的机器上做了更少的事。3.2 排序解法的注意事项这个解法看似简单细节里全是坑。第一个坑排序会改变原数组。如果你在其他语言里用的是传引用C 默认sort就是原地排那么调用完containsDuplicate外部传进的数组就已经被改了。很多实际场景里你只是“检查一下”并不希望数据被重排。有两种应对一是在函数内拷贝一份再排序代价是额外 O(n) 空间二是事先明确这个函数的副作用在注释里写清楚“会修改输入数组”。面试的时候我建议主动提一句“这个解法会改变原数组如果面试要求不能修改原数组我需要先拷贝一份”这会让面试官觉得你有工程意识。第二个坑C 的std::sort是不稳定排序。这道题对稳定性没有要求因为相等元素是否保持相对顺序完全不影响“是否存在重复”这个判断。但如果你在别的题里用“先按 A 排序、再按 B 排序”的技巧必须注意std::stable_sort才是稳定排序。这是很多人在其他题目上翻车的经典原因在这道题里倒是无关紧要。第三个坑面试官会追问“排序为什么是 O(n log n)”。很多人背过sort的复杂度但被问到底层算法是什么就懵。标准库的sort通常是内省排序IntroSort——一种结合了快速排序、堆排序和插入排序的混合算法最坏情况也是 O(n log n)。你能把这个讲明白面试官的眼神会变。3.3 排序解法的隐藏优势哈希表解法空间 O(n)排序解法空间 O(1)原地排序的话。如果面试官说“我希望空间复杂度尽可能低数组可以被修改”那排序解法就是最优解。这个伏笔在后面“追问”环节会很有用。另外排序解法其实给后续变种题打了个底。比如“找出数组中第一个重复出现的元素”“找出出现次数最多的元素”排序之后都变成了线性扫描问题。排序是一种通用预处理它解决的不止一道题而是一类题。4. 哈希表才是这题的标准答案空间换时间的经典权衡终于说到面试中最常被期望说出的解法了。思路很简单遍历数组把每个元素放进一个集合里。如果放的过程中发现“这个元素已经在集合里了”就说明有重复。bool containsDuplicate(vectorint nums) { unordered_setint seen; for (int num : nums) { if (seen.count(num)) { return true; } seen.insert(num); } return false; }一次遍历每个元素的插入和查找在平均情况下都是 O(1)所以整体时间复杂度O(n)空间复杂度O(n)。4.1 为什么是unordered_set而不是set这个点值得展开说因为太多人栽在这上面了。C 标准库里有两个容器可以“存不重复元素”std::set和std::unordered_set。std::set的底层是红黑树一种自平衡二叉查找树插入、查找、删除都是 O(log n)。好处是有序可以快速找前驱后继、范围查询。std::unordered_set的底层是哈希表插入、查找在平均情况下是 O(1)。坏处是无序而且最坏情况下哈希冲突严重会退化到 O(n)。在这道题里我们只需要“判断存在性”完全不需要“有序”这个特性所以unordered_set是明显更合理的选择。如果你的代码里用了set面试官很可能会追问“为什么不用unordered_set”——你要是答不上来分数直接扣一截。反过来如果面试官问“能不能用multiset”答案是可以但没必要。multiset允许重复元素判断是否有重复可以插入后看count 1但这个容器比set更重语义也不直接属于“能用但不是最优设计”。4.2 哈希表背后的原理拉链法与负载因子面试官如果继续深入通常会问哈希表本身。哈希表把元素通过哈希函数映射到一个数组下标桶上。不同的元素可能映射到同一个桶这就是哈希冲突。最常见的解决方式是链地址法拉链法每个桶背后挂一个链表或红黑树冲突的元素都放在这个桶的链表里。当链表过长时查找效率就会下降。所以哈希表有一个负载因子元素个数 / 桶个数的概念超过阈值C 标准库通常默认 1.0就rehash——也就是扩容重新分配桶重新计算所有元素的哈希位置。这就是为什么unordered_set的平均操作是 O(1)但最坏情况是 O(n)如果哈希函数设计得极差所有元素都映射到同一个桶那哈希表就退化成一个链表查找就是线性扫描。有个工程细节如果你提前知道数据量很大可以reserve预留空间减少 rehash 带来的开销。unordered_setint seen; seen.reserve(nums.size());这一行代码在小数据量下无所谓但如果nums有上百万个元素能显著减少扩容带来的性能损耗。面试时写这一行绝对是加分项——它说明你了解哈希表的行为而不只是会用 API。4.3 早期返回的收益与陷阱哈希表解法还有一个容易被忽略的工程点如果重复出现得很早能不能提前退出能。上面代码里一发现count为真就return true这就是提前退出。最好情况下前两个元素就重复跑两次循环就完事。但这里有个陷阱如果你把“全部插入完再统一判断”写成两遍循环比如先全部insert然后再遍历一遍数count那一个 O(n) 的操作就变成了 2n虽然复杂度还是 O(n)但常数因子翻倍了。更重要的是当你用哈希表做存在性判断时一边插入一边检查几乎是唯一正确的姿势——你想想如果重复的元素在数组前面你全部插完再查岂不是白跑一趟这个“边插边查”的模式在很多哈希表相关的题目里都会出现比如“两数之和”“最长连续序列”都是一样的套路。其实这就是一个通用模板遍历每个元素 如果当前元素在集合里找到重复返回 否则把当前元素加入集合可以说这道题不只是考你知不知道哈希表更是考你知不知道哈希表在存在性判断里的标准用法。5. 不那么常见但偶尔有奇效的思路鸽巢原理与位图法前面的解法都是“通用武器”。但面试官如果觉得前面几关你都轻松过了可能会给一个看起来像是“增加难度”的前提限制这时候就需要一点不那么通用的武器。5.1 鸽巢原理能不能在遍历之前就“截胡”鸽巢原理也叫抽屉原理说得很直白如果你有n 1只鸽子要放进n个鸽巢那至少有一个巢里有两只鸽子。套到这道题里如果数组的每个元素都被限制在区间[0, n-1]之间而数组长度也是n那么只有两种情况——要么所有元素正好是0到n-1各出现一次要么必然有重复。这题目常出现的变体版本就是给定的数组长度为 n元素取值在 [0, n-1] 范围内请判断是否有重复元素。有了这个限制条件一个很妙的做法就出来了把每个元素放到它“应该在”的位置上。元素x应该放到下标x的位置。如果发现目标位置已经放着正确的元素那就有重复了。bool containsDuplicate(vectorint nums) { int n nums.size(); for (int i 0; i n; i) { while (nums[i] ! i) { if (nums[nums[i]] nums[i]) { return true; } swap(nums[i], nums[nums[i]]); } } return false; }这个解法的时间复杂度是 O(n)每个元素最多被交换两次空间复杂度是 O(1)而且不需要额外哈希表。它的本质是把数组本身当作哈希表来用——元素值就是它的哈希位置。面试时能写出这个解法基本等于告诉面试官你不仅会背哈希表还理解哈希表的本质是“位置映射”。但注意这个解法有一个重要前提元素值必须在[0, n-1]范围内。如果超出这个范围就得先做偏移或者映射。面试中如果题目给了这个限制这个解法几乎是最优的——时间 O(n)、空间 O(1)、无副作用。5.2 位图法当内存吃紧的时候怎么办回到通用版本如果面试官说“数据量非常大比如几亿个整数内存放不下一个完整的unordered_set你怎么办”一个经典思路是位图bitmap。假设你知道元素的值域范围比如所有整数都在[0, 10^9]之间你可以开一个对应大小的位数组每个位表示“这个值是否出现过”。遍历数组如果对应位已经是 1说明重复否则置为 1。位图相对于哈希表的优势是极低的常数空间一个位只占 1 bit。比如要标记 1 亿个可能的整数只需要约 12 MB 内存而存 1 亿个int的unordered_set轻松超过 1 GB。C 里可以用std::vectorbool——虽然这个东西在设计上有争议但当作位图用是完全可以的。也可以用bitset但bitset要求编译期确定大小不适合运行时才知道值域范围的场景。bool containsDuplicate(vectorint nums, int valueRange) { vectorbool bitmap(valueRange 1, false); for (int num : nums) { if (bitmap[num]) { return true; } bitmap[num] true; } return false; }时间复杂度依然是 O(n)空间取决于值域范围而不是元素个数。不过这个解法有个明显前提值域不能太大而且不能有负数或者说负值需要做偏移。如果值域是[-10^9, 10^9]你需要 2×10^9 个 bit约 250 MB 内存——倒不是不可接受但便宜占得就有限了。所以实际面试中位图解法更多是作为一个“思考方向”被提及而不是首选。5.3 这些“歪招”的真正价值说实话这题你面试时用不着把鸽巢原理和位图法全部写出来。但这些思路的存在证明了同一个问题可以有不同的切入角度暴力从定义出发比较所有元素对排序从结构出发利用序关系简化判断哈希从记忆出发用空间换时间鸽巢从数学出发利用值域信息提前剪枝位图从工程出发针对大数据量压缩存储每个角度都有自己的适用场景。“暴力美学”这四个字说的不是某一种解法而是这种不断换个角度看同一个问题的过程本身——它是有美感的。6. 面试官视角这道题怎么答才算“剑斩OFFER”最后聊聊实战。我面别人也好帮朋友模拟面试也好这道题出现的频率相当高因为它太适合用来区分“背题的”和“真会的”。6.1 面试中推荐的作答路径不要一上来就甩哈希表。我建议的答题节奏是第一步确认题意。复述一遍“我要判断数组里是否有任一元素出现至少两次返回布尔值。”如果有必要问清楚数组长度范围、元素值域、是否允许修改原数组。这步很基础却能让面试官看到你的沟通习惯。第二步先给暴力解。简单说一句“最简单的方法是两两比较时间复杂度 O(n²)空间 O(1)”并快速写出代码或伪代码。这不是浪费时间——它向面试官证明你的思考是从正确性出发而不是从背诵出发。第三步自己指出问题。“这个解法在 n 很大时过不了我们来优化。”然后给出排序思路“可以先排序再检查相邻元素时间复杂度降到 O(n log n)空间 O(1)。但它的前提是可以修改原数组。”第四步再进一步到哈希表“用unordered_set一边遍历一边查平均 O(n) 时间O(n) 空间。这是这道题理论上的最优时间。”写出完整代码。第五步补充边界条件。“空数组、单元素数组、负数、重复元素在开头和结尾的情况这个实现都能正确处理。另外如果要保留原数组我会先拷贝一份再排序。”这一套下来面试官看到的不是“一个人背了一道题”而是一个有分析路径、有复杂度意识、有工程判断力的候选人。这才是“剑斩OFFER”的真正含义——你不是靠记住答案打败对手而是靠展示思维方式碾压对手。6.2 常见的追问与应对面试官在收到哈希表答案后很可能追问如下几个问题“如果不能用额外空间怎么做”答排序。sort后检查相邻元素原地排 O(1) 空间。前提是允许修改数组。“如果不允许修改原数组呢”答那只能哈希表或者拷贝一份再排序。到这里面试官其实就在引导你比较时间-空间的 trade-off。“如果数据特别大内存放不下哈希表怎么办”答可以考虑位图如果值域可控或者分布式思路、外部排序——看你假设的场景。对这道题而言提位图就够了分布式一般不会在这里展开。“如果要求返回第一个重复的元素呢”答哈希表天然适合遍历时第一次发现“已在集合中”的那个元素就是第一个重复的。排序解法就看不出这个了。“如果重复元素可能有很多个找出现次数最多的元素呢”答哈希表统计频次遍历一遍找最大值。这个扩展就自然转移到了“数组中的众数”这类题。每一个追问本质上都在测试你对数据结构特性的理解有多深。你能接住追问这道题才算真正答完。6.3 关于“暴力美学”我的真实理解回到标题里的四个字——“暴力美学”。很多人以为这四个字说的是暴力解法本身很美。但真刷过题、真面过试的人应该明白暴力解法的美不在于它快而在于它定义了一个起点。所有优化都是你从起点出发一步步发现“这里有冗余”“这里可以用空间换时间”“这里可以借用数学性质”最终走到一个优雅解的过程。没有暴力解你连起点都没有。所以我特别鼓励准备面试的人拿到一道题先别急着回忆“我是不是刷过这道题”。先老老实实想最笨的办法然后从最笨的办法出发问自己三个问题慢在哪找瓶颈有没有办法消掉这些瓶颈换数据结构 or 换算法这些优化牺牲了什么空间稳定性原数组你把这三个问题走完这道题就算彻底吃透了。“存在重复元素”这种简单题都吃透了后面那些复杂题无非是把这套思维用得更复杂一点而已。7. 变种题与延伸一道题打通一个系列说点实际的——面试官出“存在重复元素”的时候往往不会只考这一道。他手里还有两个经典变种随时准备顺着你的答案继续往外掏。7.1 变种一存在重复元素 II219 题题面也简单给定数组问是否存在两个相等的元素并且它们的下标的差的绝对值不超过 k。这题的暴力解法就是双重循环加一个下标差判断但最优解是在哈希表基础上加个滑动窗口的思想遍历数组维护一个大小为 k 的窗口。每次只看窗口内有没有当前元素。窗口可以用unordered_set模拟每次遍历到新元素先查 set有就返回 true然后插入当前元素如果 set 大小超过 k就删掉最早加入的那个元素。bool containsNearbyDuplicate(vectorint nums, int k) { unordered_setint window; for (int i 0; i nums.size(); i) { if (window.count(nums[i])) { return true; } window.insert(nums[i]); if (window.size() k) { window.erase(nums[i - k]); } } return false; }这题考的是有界窗口和“如何删除过期数据”。很多人在erase(nums[i - k])这一步卡壳——这里的本质是每次窗口移动一格就要把窗口最左边的元素踢出去。你要是能答出来面试官基本确认你的哈希表不是白刷的。7.2 变种二存在重复元素 III220 题这题难度直接拉满给定数组问是否存在两个元素它们的值差的绝对值不超过 t且下标差的绝对值不超过 k。这题最优雅的解法是桶排序思想把每个元素按值分桶桶的大小设为 t1。如果两个元素被分到同一个桶那它们的值差一定不超过 t如果相邻桶还需要再比较一下。这题用unordered_map实现桶即可。bool containsNearbyAlmostDuplicate(vectorint nums, int k, int t) { unordered_maplong, long buckets; long bucketSize (long)t 1; for (int i 0; i nums.size(); i) { long num nums[i]; long bucketId (num - INT_MIN) / bucketSize; if (buckets.count(bucketId)) return true; if (buckets.count(bucketId - 1) abs(num - buckets[bucketId - 1]) t) return true; if (buckets.count(bucketId 1) abs(num - buckets[bucketId 1]) t) return true; buckets[bucketId] num; if (i k) { long oldBucketId ((long)nums[i - k] - INT_MIN) / bucketSize; buckets.erase(oldBucketId); } } return false; }这个解法里面最值得琢磨的是“按值分桶”的思想——它把一个“差值限制”问题转化成了“同桶或邻桶”问题。当你从“存在重复元素”一路走到这里回头看你会发现这套题其实在讲一件事如何根据不同的约束条件设计不同的查找结构。7.3 刷题策略把一道题当成一个系列来学我见过很多刷题的人按题号一题一题往后做做完 217 就看 218做到 219 发现“哦这题跟 217 不一样”然后又从零开始想。这样的效率其实很低。更好的做法是按主题、按系列刷。拿到“存在重复元素 I”就主动把 II 和 III 也做了。这样你不仅掌握了一道题你还掌握了一类问题的演化路径。面试的时候面试官从 217 追问到 219再到 220你不是“遇到新题”而是“复习旧知识”——心态完全不一样。这也是我在这篇文章最后最想强调的一点暴力美学的终点是你在各种解法之间自由切换、游刃有余的状态。到了那个状态任何一道面试题不管是简单的还是复杂的都只是你思维路径上的一个普通节点而已。我在实际面试别人时最怕的不是候选人不会做难题而是候选人只会背答案。会背哈希表的答案、会写出unordered_set的代码不等于理解哈希表为什么能解决这个问题。你试试在“存在重复元素”这道题上把每个解法的时间复杂度、空间复杂度、适用前提都能讲清楚把面试官的问题从暴力问到哈希、从哈希问到鸽巢原理、从鸽巢原理问到变种题——你就知道什么叫“一剑斩落OFFER”了。