从暴力到异或:算法题“消失的数字”四种解法与优化路径 做算法题的人大概率都遇到过这样一道经典题给你一个长度为n的数组里面的数字是0到n之间所有整数但恰好缺了一个让你找出“消失的数字”。这道题在网上很常见力扣上面也有原题但它的价值远不止“一道入门题”这么简单——同一个需求从暴力遍历到位运算能写出至少四种思路完全不同的解法而每一种解法背后都对应一种典型的算法思维。这篇文章我会把这四个方案逐个拆开讲不只是贴代码更想把每套方案“为什么会想到”“复杂度到底差在哪”“边界情况怎么踩坑”这些真正影响面试表现的东西讲透。适合刚刷题的新手也适合准备面试、想系统整理常见解法的朋友看完你能对“暴力解 → 哈希表 → 数学 → 位运算”这条优化路径有非常直观的理解。1. 题目到底在问什么先读懂题干再谈优化1.1 原题描述与样例先看看题目的标准描述。给定一个包含n个整数的数组数组元素都在[0, n]这个范围内并且每个整数只出现一次但因为数组只有n个位置所以里面一定缺了一个数字。要求找出这个缺失的数字。举个例子说明。如果n 3数组是[3, 0, 1]那0到3应该是{0, 1, 2, 3}数组里出现了0、1、3缺的就是2。再比如n 2数组是[0, 1]那缺失的就是2注意缺失的可能是最大的那个数字这个细节很多人第一次写会忽略。题目保证数组中的每个数字都不重复这是两个很重要的前提第一长度是n范围是0~n一共n1个数第二这n1个数中只有一个没出现在数组里。这两个前提直接决定了后面很多解法能不能用。1.2 题干里真正有价值的三个约束我每次拿到题目都会先划三个重点这道题也不例外数字范围是 0 到 n。这个范围不是随便给的它意味着所有可能的数字刚好比数组长度多一个天然形成了一种“索引和值”的对应关系后面位运算方案就是靠这一点破局的。所有数字都不重复。如果允许重复题目难度直接上升一个级别很多方案也会失效。不需要保证数组有序。题干并没有说输入是排好序的所以任何“排序后相邻检查”的做法都需要自己先排序不能假设输入已经有序。从这几个约束可以看出这道题真正考察的不是“会不会写循环”而是“能不能根据数据特征选择合适的策略”。暴力解谁都会但只有理解了约束条件才能想到数学公式和异或这种降维打击的写法。1.3 第一直觉暴力遍历为什么不可取如果你第一次接触这道题最自然的想法肯定是两层循环对于0到n中的每个数都去数组里找一遍如果哪个数找不到它就是答案。这个思路完全正确但时间复杂度是O(n^2)在n稍微大一点的时候就很难看了。不过暴力解并不是没有价值。我自己刷题的经验是遇到任何新题先把暴力解写出来哪怕它就两三层循环也能帮你理清“我到底在找什么”。这道题暴力解的核心是“查找”而查找的优化方向天然有两个排序后二分、用哈希表。所以后面方案一的排序和方案二的哈希表本质上都是对暴力查找的升级。1.4 什么时候应该追求更优解很多新手会问暴力能过为什么还要优化我的看法是刷题和在真实项目里写代码不太一样。项目里可能一个函数一辈子只跑一次暴力解也就那样但算法题考察的正是你对复杂度、数据结构的敏感度。尤其是这道题面试时面试官大概率会追问“能不能不用额外空间”“能不能只遍历一遍”这就是在引导你从哈希表走向求和和异或。所以我的建议是暴力解用来保底和理解题意但至少要把下面四种方案都过一遍面试时才能有底气地说出“我能给 O(n) 时间、O(1) 空间、并且不修改原数组的方案”。2. 方案一排序后线性扫描最直观但最容易被细节反杀2.1 基本思路排序方案的思路非常简单先把数组从小到大排好序然后让索引i从0开始遍历如果nums[i]不等于i说明i就是缺失的数字。如果遍历完所有元素都相等那缺失的数字就是n。举个例子数组[3, 0, 1]排序后变成[0, 1, 3]遍历到i 2时发现nums[2] 3不等于2返回2。数组[0, 1]排序后还是[0, 1]遍历完没发现缺失返回n 2。这个方案虽然简单但有一个容易忽略的问题排序会改变原数组。有些题目会要求不能修改输入数组这时候排序方案就被一票否决了。2.2 代码实现与注释def missingNumber(nums): nums.sort() n len(nums) for i in range(n): if nums[i] ! i: return i return n这段代码里最后一行特别关键。很多人会写成range(len(nums))之后就忘记处理“缺失的是最后一个数”的情况。比如nums [0, 1, 2]排序后遍历完三个位置都相等如果函数没有最后的return n就会隐式返回None直接报错或提交失败。C 的写法也类似注意排序用sort(nums.begin(), nums.end())然后同样遍历。2.3 复杂度与适用场景排序方案的时间复杂度取决于排序算法。常见的快排或归并是O(n log n)空间复杂度如果用的是原地排序就是O(1)。但要注意如果语言底层使用了递归快排栈空间也可能会被算进空间复杂度。这个方案最适合的场景是题目不要求最优时间、也不要求不修改数组你只是需要一个“绝对不可能写错”的保底解法。但它的短板也很明显时间上比O(n)的方案差了一个档次修改了原数组如果后续还要用原数据就麻烦了排序本身是个“重操作”在面试官看来不够优雅。2.4 容易被排序坑到的两个细节排序方案踩坑的点有两个。第一个是上面说的返回值问题必须检查“缺失最大值”的情况。第二个是不要手写排序。我见过有同学为了显得自己厉害在代码里手写快速排序结果边界写错本来能过的题反而超时。老老实实用语言自带的排序函数就好刷题阶段不要在这种地方炫技。另外一个思考题如果排序后使用二分查找能优化吗可以的因为有序数组里找第一个nums[i] ! i的位置本质上可以用二分能把查找部分的时间从O(n)降到O(log n)但整体复杂度依然被排序的O(n log n)主导。这个升级一般没人用因为阈值很尴尬不过作为思路拓展可以了解一下。3. 方案二哈希表/计数数组典型的空间换时间3.1 为什么哈希表能解决问题既然暴力解的问题是“查找太慢”那就直接上查找的标配——哈希表。思路是先把数组里所有数字都放进一个集合然后逐个检查0到n哪个不在集合里。哈希表的查找是平均O(1)的所以整体时间降到O(n)代价是需要O(n)的额外空间。但这里有个细节值得单独说一下虽然“哈希表”是这类问题的通用解但在这道题里哈希表并不是最优实现因为数字范围是确定的、连续的。既然知道范围是0到n那直接开一个长度为n1的布尔数组做计数标记比用unordered_set或set更高效、更省内存。3.2 两种实现方式对比实现方式查找速度额外空间适用场景unordered_set平均 O(1)常数较大O(n)节点开销大数字范围未知、数据稀疏vectorbool计数O(1)常数极小缓存友好O(n)但 1 bit/元素已知范围连续如本题表格里可以看到vectorbool不仅更快而且空间上更紧凑。unordered_set每个元素还要额外存哈希节点内存开销往往比计数数组大好几倍。3.3 代码实现def missingNumber(nums): n len(nums) seen [False] * (n 1) for num in nums: seen[num] True for i in range(n 1): if not seen[i]: return i这个写法非常直白第一遍标记第二遍查找。也可以用集合的写法def missingNumber(nums): num_set set(nums) n len(nums) for i in range(n 1): if i not in num_set: return i两者都能过但实测下来布尔数组通常比集合快 20% 到 30%因为数组的连续内存访问对 CPU 缓存更友好。3.4 空间换时间的边界思考哈希表方案的优点是思路简单、几乎不可能写错即使题目条件变化比如数字可能重复只需要稍微调整也能用。但缺点也很明确用了O(n)额外空间这在很多面试题里是被追问的点。面试时如果你只写出哈希表方案面试官大概率会问“能不能不用额外空间”。这时候就可以顺着话头过渡到求和或者异或。我比较推荐在面试中把哈希表作为“第一层优化”来讲它展示的是你懂数据结构但不要止步于此。还有一个容易被踩的坑如果你用vectorbool或list[False]标记数组长度必须是n1因为数字范围是0到n共n1个数。少开一个位置最后一个数就会数组越界。这个细节在本地测试小样例时可能测不出来但在 LeetCode 上会直接报错。4. 方案三高斯求和一行代码的数学解法4.1 思路来源从 0 加到 n如果我告诉你这道题其实不需要知道数组里的具体数字你信吗0到n的和是固定的可以用等差数列求和公式直接算出来。然后我们把数组里所有数字加起来两者相减差值就是缺失的数字。这个思路特别像“把 1 到 100 的和算出来再减去你能看到的所有数字剩下的就是被藏起来的那个”。等差数列求和公式是S n * (n 1) / 2这里要注意公式里n是数组长度但求和范围是0到n一共有n1个数。因为多加了一个0不影响结果所以直接用n*(n1)/2即可。4.2 推导过程与数学直觉完整的推导过程可以这样理解。如果数组长度为n完整的序列应该是0, 1, 2, ..., n共n1个数它们的总和是0 1 2 ... n n * (n 1) / 2然后用这个总和逐个减去数组中的元素剩下的就是缺失值。换个角度看也可以先求数组的和再用公式总和减去数组和效果一样。数学上这个方法的前提是数组中的数字恰好是完整序列去掉一个数所以差值一定精确等于缺失值。4.3 代码实现与溢出处理def missingNumber(nums): n len(nums) total n * (n 1) // 2 return total - sum(nums)就这么几行非常优雅。但这里有一个隐藏得很深的问题溢出。在 Python 里整数可以无限大所以没什么问题。但在 C 或 Java 里n * (n 1) / 2可能直接爆int。我记得题目给的n上限如果比较大n^2会轻松超过 2^31这时候如果不用long long算出来的总和是个错得离谱的值最后结果自然不对。安全的写法是int missingNumber(vectorint nums) { int n nums.size(); long long total 1LL * n * (n 1) / 2; long long sum 0; for (int num : nums) sum num; return (int)(total - sum); }用long long就能覆盖绝大多数情况。另外还有一个防溢出的技巧不用一次性算出完整总和而是在遍历数组的同时用total逐个减掉当前元素这样可以避免先加一个巨大的总和再减的中间值过大。但严格来说long long已经足够安全不需要过度设计。4.4 求和方案的适用边界求和方案非常漂亮但它有一个隐含前提只缺一个数字。如果题目改成“缺两个数字”求和就只知道缺失数字的和但无法确定是哪两个。这时候需要再加一个约束比如平方和才能联立方程解出来。另外如果题目允许数组中有重复数字求和方案也会失效因为总和差值不再等于缺失值。所以在面试中讲完求和方案后如果能主动提一句“这个方案的前提是只缺一个且不重复”会显得你对问题的理解更深入。4.5 一句话总结数学方案的价值我觉得数学方案最大的价值还不是省空间而是它让你意识到很多列表问题并不需要真的“查”数据结构直接用数学性质就能一步到位。这也是为什么我建议刷题时多想一想“这题有没有数学解法”往往会有意外收获。5. 方案四异或真正的点睛之笔5.1 为什么看到“成对”会想到异或异或XOR是位运算里非常特别的一个操作它有三个性质a ^ a 0一个数和它自己异或等于 0a ^ 0 a任何数和 0 异或等于它自己交换律和结合律顺序怎么调整都不影响结果。这三点组合在一起就产生了一个很巧妙的效果成对的数字会彼此抵消。如果你把一堆数字全部异或起来出现两次的数字会变成 0出现一次的数字会被留下来。在这道题里数组里有n个数字完整序列有n1个数字。如果我们把数组里的数字和0到n的所有索引全部异或一遍缺失的那个数字只出现了一次其他所有数字都会出现两次而被抵消最终结果就是缺失值。这个思路简直是专门为这题准备的。5.2 推导与证明我们来一步步推导。假设数组长度为n元素是[a_1, a_2, ..., a_n]完整序列是[0, 1, 2, ..., n]。把数组里的所有元素和完整序列的所有数字放在一起一共是2n1个数。除了缺失数字x之外每个数字都恰好出现两次。根据异或的自反性成对出现的数字异或后都会变成 0。所以(0 ^ 1 ^ 2 ^ ... ^ n) ^ (a_1 ^ a_2 ^ ... ^ a_n) x这个等式右边的x就是缺失的数字。那怎么在代码里实现“数组元素和完整序列全部异或”一个小技巧是遍历数组的时候把nums[i]和索引i同时异或进去遍历结束后再异或一个n就等于把0到n的索引也全部纳入了。5.3 代码实现def missingNumber(nums): res 0 n len(nums) for i in range(n): res ^ nums[i] res ^ i res ^ n return res这段代码非常短但每一步都有数学依据。模拟一个例子nums [0, 1, 3]n 3。循环中res依次异或0^0、1^1、3^2最后异或3。注意这里3在数组中出现过一次在最后一步又出现了一次会抵消2只出现在索引里没有配对所以最终结果是2。C 版本一模一样唯一的区别是返回值类型用int。5.4 异或方案的优势异或方案最大的优点是时间复杂度 O(n)、空间复杂度 O(1)、不修改原数组、不存在溢出风险。这四个特性同时满足在很多面试场景下这就是标准答案。和求和方案比异或不需要考虑大数溢出和哈希表比异或不需要额外空间和排序比异或速度更快而且不改数据。三个优势叠加让它成为这道题的最佳解。5.5 如何向面试官解释异或解法面试时不要让场景冷场可以用这种口吻解释“因为相同的两个数异或后为 0而 0 异或任何数等于它本身。我把数组里的数跟 0 到 n 的所有下标全部异或一遍缺失的那个数出现一次其他数都出现两次自动抵消剩下的就是答案。”面试官如果追问“为什么不会错”你就补一句“这是交换律和结合律保证的顺序无关结果唯一”。这个回答基本可以把异或方案的原理讲透。6. 四个方案对比与刷题心得6.1 核心指标对比表方案时间复杂度空间复杂度是否修改原数组溢出风险代码难度排序 遍历O(n log n)O(1)是无低哈希表/计数数组O(n)O(n)否无低高斯求和O(n)O(1)否有需 long long极低异或O(n)O(1)否无中从表里能直观看到异或在所有指标上都是最优的这也是为什么它被当作标准解。但值得注意的是求和方案代码最短如果面试时被要求“写出你能想到的最简洁解法”用求和往往最快。6.2 面试场景怎么安排答案顺序我个人的建议是不要上来就甩最优解那样反而会让人觉得你是背过答案。正确顺序应该是先说最直观的哈希表展示你有基本的数据结构能力然后说既然数字范围确定、只缺一个可以用高斯求和展示你有数学敏感度再说求和可能溢出于是升级到异或展示你考虑问题的全面性最后可以提一句“如果允许排序且不在意修改输入排序也是可行的”收个尾。这样一层一层递进面试官能清楚看到你的思考过程。这是我在多次面试和模拟面试里验证过的表达节奏。6.3 刷题时怎么利用这类“多解法”题目很多同学刷题时做出一道就跑了这样其实效率不高。像“消失的数字”这种天生多解的题目最适合用来练习“一题多解”。每写完一种解法都问自己三个问题我的解法时间和空间复杂度是多少它依赖题目里的哪些特殊条件如果去掉一个条件这个解法还能用吗比如去掉“不重复”条件求和和异或都会失效哈希表还能用去掉“连续范围”条件计数数组也要改。这种推演能帮你把每类解法的适用范围刻在脑子里面比盲目刷十道题更有用。6.4 我踩过的坑这道题看起来简单但我当初刷的时候也交过几次学费。第一次用了纯暴力超时第二次用排序结果忘了处理“缺最大值”第三次用求和C 里忘了加long long大样例直接 WA。现在回头看这三次错误其实对应着三个非常典型的坑复杂度分析不到位、边界检查不严、类型溢出不注意。写题时提前把这些坑防住基本就能保证通过率。还有一个容易被忽略的点如果用异或解法循环范围千万不要写成range(n1)的索引再访问数组因为数组长度只有n访问nums[n]会越界。异或索引和访问数组是两码事要分开写清楚。7. 常见问题与排查技巧实录7.1 常见的 WA 原因这道题提交失败的几大原因我整理了一下绝大多数都离不开以下几种错误类型原因排查方法返回 None没处理缺失 n 的情况在函数末尾补return n越界哈希表数组开成 n 而不是 n1检查数组长度是否等于范围长度溢出C 用 int 求 n*(n1)/2分母先除或改用 long long超时用了 O(n^2) 暴力换哈希、求和或异或这些坑都很隐蔽单独跑小样例时基本看不出来因为数据量小、数值也小。所以我强烈建议提交之前先自测几个边界。7.2 必测的边界用例不管用哪种方案我都建议先跑这四个用例[0]长度为 1范围是 0 和 1缺的是 1[1]缺的是 0[0, 1]缺的是 2[1, 2]缺的是 0。这四个用例分别覆盖了“缺最大值”“缺最小值”“普通中间缺”“最小值缺失”四种情况。尤其是[0]和[1]你光看代码可能觉得无所谓但排序方案和哈希表方案在这里最容易出问题。7.3 单步调试的技巧如果你写的是 Python可以用下面这种带中间输出的方法快速定位问题def missingNumber(nums): res 0 n len(nums) for i in range(n): res ^ nums[i] print(fstep1: i{i}, nums[i]{nums[i]}, res{res}) res ^ i print(fstep2: i{i}, res{res}) res ^ n print(ffinal: res{res}) return res在本地跑一遍nums [3, 0, 1]观察每一轮res的变化可以非常直观地看到成对的数字是怎么被抵消的。这一步比干看代码更能加深理解。7.4 当 n 特别大的时候这道题有时候会在测试用例里放一个特别大的n比如十万、百万级别。这种情况下排序方案可能勉强能跑但哈希表的额外内存开销会变得明显求和方案要格外小心溢出异或方案则完全不受影响。所以如果你不喜欢处理边界直接用异或就是最省心的选择。另外一个极端是n 0数组为空。这种情况应该返回0因为范围是0到0数组里没有数字缺的就是 0。四种方案里异或和求和都能正确处理排序方案也基本不会出错主要看代码实现有没有“空数组”的防御。我个人刷这道题的真实体会是别急着炫技先把最暴力的解法写对感受一下问题到底难在哪然后一步步从哈希表升级到求和、再到异或。这个递进的过程本身比最终答案更有价值。真正面试的时候能把四个方案的来龙去脉和取舍讲清楚比直接背出最优解更让人信服。最后再分享一个小技巧本地写完代码一定要先测[0]、[1]、[0,1]这三组输入这道题几乎所有的坑都可以在这三组数据里暴露出来提前抓住它们线上提交就是一次过。