昨天和准备春招的学弟聊算法题他突然问我“LeetCode 268 缺失数字这题你会几种解法”我说五种起步他当场愣住。很多人看到“Easy”直接跳过但这其实是被严重低估的经典题——数组里从 0 到 n 本来有 n1 个数现在给你其中 n 个数找出缺失的那个。表面上一行求和就能出答案背后却藏着枚举、排序、哈希、位运算、数学建模五条完全不同的路。今天的“每天学习一点算法”就把这题掰开揉碎讲清楚每种解法的原理、代码、复杂度和面试话术。无论你是刚开始刷题的萌新还是准备二刷常考题的老手这篇都能用得上。1. 别小看这道“送分题”题目长什么样坑在哪里1.1 先看题面和核心约束原题出自 LeetCode 268Missing Number题面简洁得不像话给定一个包含 n 个不同数字的数组 nums数字取自范围 [0, n]包含 0 和 n找出范围中缺失的那个唯一数字。示例很好理解nums [3, 0, 1]n 3完整范围是 {0, 1, 2, 3}缺失的是 2nums [0, 1, 2]n 3完整范围是 {0, 1, 2, 3}缺失的是 3nums [0]n 1完整范围是 {0, 1}缺失的是 1nums [1]n 1完整范围是 {0, 1}缺失的是 0。注意最后两个例子缺口不一定在中间也可能在开头或者结尾。很多人第一次做这题就下意识以为“肯定少了一个不算大的数”结果边界情况被 n 和 0 卡住。题面里还有三个隐藏前提数字互不重复、只有一个缺失、范围从 0 开始而不是从 1 开始。这三条如果改动任意一条解法都会天差地别——后面我会专门展开。1.2 这道题究竟在考什么先泼一盆冷水这道题表面考“找缺失”实际上考的是三件事。第一你能不能识别出“数组元素和下标天然存在一一对应关系”这个规律。0 到 n 范围内的数放到长度为 n 的数组里恰恰只有一个位置被“拆散”这是后续所有巧妙解法的基石。第二你对常见算法套路有没有形成肌肉记忆。枚举、排序、哈希、位运算、数学公式每一种都是一个更大的算法家族的代表这道题只不过是把它们集合在一个简单场景里了。第三你能否在面试中按“暴力思路 → 逐步优化 → 最优解 → 边界条件”的顺序把一个 Easy 题讲出体系感。我做过几次模拟面试官问这题时最明显的感受是能直接背出异或解法的人不少但能从头把思路推到异或解法的人很少。面试官要看的恰恰是后者。这也提醒我真正把一道题吃透不是背过某个最优解而是知道它为什么“最优”。下面就从最笨的办法开始推。2. 热身解法暴力枚举、排序与哈希表2.1 暴力枚举一切算法的起点拿到题最容易想到的方法就是“一个一个试”对 0 到 n 的每一个数去数组里扫描一遍看它在不在。找不到的那个就是缺失数字。def missingNumber(nums): n len(nums) for target in range(n 1): found False for x in nums: if x target: found True break if not found: return target这个写法的时间复杂度是 O(n²)空间复杂度 O(1)。数组只有几十个元素时跑起来没感觉一旦 n 到十万级别基本原地爆炸。但它有个好处逻辑绝对正确而且写出来只需要一分钟特别适合在面试开头用来“立一个基线”让面试官知道你不是只会背答案而是真的从问题本身出发思考。我在实际刷题中反而建议遇到任何题目先别急着想最优解把暴力解法老老实实写一遍哪怕它慢。这个过程能帮你确认自己对题意的理解没有偏差也方便之后在复杂度分析时形成对比。直接跳最优解很多时候会因为边界条件想漏而出 bug。2.2 排序法借下标说话第二种思路是排序。先把数组排好序然后遍历一遍如果某个下标 i 上的元素不是 i那 i 就是缺失的数字如果 0 到 n-1 的位置全部对得上缺失的就是 n。def missingNumber(nums): nums.sort() for i in range(len(nums)): if nums[i] ! i: return i return len(nums)时间复杂度 O(n log n)空间复杂度取决于排序算法是否原地。Python 默认的 TimSort 是 O(n) 额外空间C 的 std::sort 是原地排序O(log n) 的栈空间。这个解法的亮点在于它把“找缺失”转化成了“检查下标和值是否错位”而这个思路是后面很多进阶题比如找重复数、找第一个缺失正数的核心模板。代价也很明显排序破坏了原数组的相对顺序。如果题目附加条件“不能修改原数组”这个解法直接出局。别觉得这是吹毛求疵真实面试中“能否修改输入数组”这半句话经常就是区分一轮面试过不过的细节。2.3 哈希表空间换时间的标准答案第三种方法是把数组元素全部塞进一个 Set然后从 0 到 n 逐个检查第一个不在 Set 里的就是答案。def missingNumber(nums): seen set(nums) for i in range(len(nums) 1): if i not in seen: return i这套思路的时间复杂度是 O(n)空间复杂度 O(n)。相比排序法它不再改变原数组还能轻松应对“缺失多个数字”的变体场景。哈希表就是典型的空间换时间你牺牲了 O(n) 的额外存储换来了线性时间的查找。不过它的短板也很明显空间复杂度不是最优。面试官几乎一定会追问“能不能 O(1) 空间”这时候自然引出下面两把“钥匙”。所以别小看哈希表解法它是通向最优解的重要跳板也帮你建立了“查找问题先想哈希”的条件反射。3. 最优解的两把钥匙求和法与异或法3.1 高斯求和把问题交给数学0 到 n 的所有整数之和是一个等差数列可以直接用高斯求和公式算出来sum n × (n 1) / 2把公式结果减去数组里所有元素的和剩下的就是缺失的那个数字。代码简单到像在作弊def missingNumber(nums): n len(nums) total n * (n 1) // 2 return total - sum(nums)这个解法的本质是“整体思维”我不需要一个一个去核对哪个数字不在而是把完整范围的总和算出来再把现有的总和减掉差额自动暴露缺失项。时间 O(n)空间 O(1)。但这里有个面试官特别爱挖的坑溢出。在 Python 里因为整数是无限精度的n(n1)/2 怎么算都不会溢出。但换到 C、Javaint 是 32 位有符号整数n 一旦超过 46340 左右n(n1)/2 就会爆掉。就算题目输入范围通常短于这个数面试官也会追问“如果 n 很大求和公式溢出了怎么办”答案也很简单别直接算完整和而是遍历数组的同时边加边减——先把 n 加到结果里然后每次减去 nums[i] 再加上 i让中间结果始终维持在一个很小的范围从源头规避溢出。这个写法我在后面的代码部分会给出。3.2 异或解法位运算的对称美异或解法是我心里这道题的最优解没有之一。核心只有三条异或性质同一个数异或自己等于 0a ^ a 0任何数异或 0 等于它自己a ^ 0 a异或满足交换律和结合律数字之间没有顺序要求。玩法是这样把 0 到 n 的所有下标全部异或一遍再把数组里的所有值也异或一遍。因为 0 到 n 本来应该有 n1 个数数组里只装了其中 n 个数所以成对出现的数字会互相抵消成 0最后剩下的那个数就是那个没有配对成功的缺失数字。def missingNumber(nums): res len(nums) for i, num in enumerate(nums): res ^ i ^ num return res这段代码写的 res 初始值是 len(nums)也就是 n然后每次把下标 i 和当前值 num 都异或进去。我来手动演示一个例子方便你彻底理解nums [0, 1, 3]n 3正确答案是缺失 2。初始 res 3。i0num0res 3 ^ 0 ^ 0 3i1num1res 3 ^ 1 ^ 1 3两次异或同一个数等于没变因为 1 被配对消掉了i2num3res 3 ^ 2 ^ 3先把两个 3 抵消剩下 2。结果 res 2。你可以看到这个过程中每个数字的“成对痕迹”都被自动抹去最后留下的就是那个孤零零的缺失项。形象点说这就像一群人排队领号码牌号码从 0 到 n 各有一张但有一个人没来领于是最后手里唯一的号码牌就是那个缺席的人。异或法连“集合的总和”都不用算直接把多余项抖出来逻辑自洽到几乎不需要额外解释。3.3 两种最优解的对比很多刷题攻略会把求和法和异或法并列推荐但实际用起来差别不小。我用一张表总结我的个人判断对比维度求和法异或法时间复杂度O(n)O(n)空间复杂度O(1)O(1)溢出风险有需边加边减规避无代码可读性极高几行说清较高需要解释异或性质面试讲解难度低适合先讲中适合当亮点对后续题目的迁移价值一般极高Single Number 系列直通我的习惯是面试时先讲求和法因为容易理解、展示思路清晰然后补一句“如果 n 很大怕溢出可以把累加和改成边加边减”再顺势抛出异或法作为“更稳健的位运算优化”。一次回答同时展示了数学思维、边界意识和位运算功底这比单纯背一个最优解要高级得多。4. 面试现场的标准答案从问清题意到多语言实现4.1 面试官真正想看的是什么这道题在面试里出现频率非常高但说实话会写的人不少写得“像人”的不多。面试官真正想看的是你解决问题的全过程而不仅仅是最终几行代码。第一步确认约束。拿到题别闷头写先问“数组大概是多大元素是不是一定互不重复能不能修改原数组”如果数组有序解法会变成二分查找如果不能修改原数组排序法和后面的“原地标记法”就直接出局。这一步在真实面试里特别加分因为很多候选人不问直接写写出来的解法往往是错的——比如上来就排序但实际上题目的隐含测试用例不允许破坏原数组。第二步给出基线解法。不要一上来就异或先说“最笨的办法是枚举O(n²)虽然慢但保证正确”再逐步优化。这个递进过程才是面试官想听的。第三步写最优解并主动分析复杂度。边写边小声解释你在干什么比如“这里用异或因为成对出现的数字会抵消”。写完顺手把时间复杂度、空间复杂度报出来。第四步覆盖边界条件。数组长度为 0 怎么办长度为 1 但只有一个元素怎么办缺失数字是 0 怎么办缺失数字是 n 怎么办把这四类都覆盖到基本就滴水不漏了。4.2 Python、Java、C 参考实现这道题的解法跨语言差异不大核心都在异或。我用三种语言给出可运行的参考实现。Python 版本def missingNumber(nums): res len(nums) for i in range(len(nums)): res ^ i ^ nums[i] return resJava 版本class Solution { public int missingNumber(int[] nums) { int res nums.length; for (int i 0; i nums.length; i) { res ^ i ^ nums[i]; } return res; } }C 版本class Solution { public: int missingNumber(vectorint nums) { int res nums.size(); for (int i 0; i nums.size(); i) { res ^ i ^ nums[i]; } return res; } };三种语言的核心逻辑完全一致res 初始化为 n循环里用 i ^ nums[i] 把“本应该存在的一对”一起异或掉最终剩余的就是缺失数字。你哪怕只用其中一种语言刷题另两种也要能看懂毕竟现在面试手写代码经常会让你换个语言现场写。如果担心求和溢出可以这么写def missingNumber(nums): res len(nums) for i, num in enumerate(nums): res i - num return resclass Solution { public int missingNumber(int[] nums) { int res nums.length; for (int i 0; i nums.length; i) { res i - nums[i]; // 边加边减避免 n(n1)/2 溢出 } return res; } }这种写法的美感在于遍历完数组res 已经等于 (n 0 1 ... (n-1)) - (nums[0] ... nums[n-1])也就是完整和减现有和。中间结果始终在很小的数值范围内浮动不会像先算 n(n1)/2 那样瞬间撑爆 int。我个人更推荐这个版本应对面试追问它同时兼顾了直观性和健壮性。4.3 复杂度分析与追问应对写完代码后面试官基本会按这个节奏追问第一个问题“现在的时间复杂度和空间复杂度是多少”答案是 O(n) 时间和 O(1) 额外空间。注意说“额外空间”这个词面试官很在意你分不清输入数组的空间和解题额外开的空间。第二个问题“能不能尝试其他思路”这时你可以补一句如果数组本身有序用二分查找找到第一个 nums[i] i 的位置时间复杂度可以降到 O(log n)。这个解法虽然前提苛刻但提出来会显得你视野开阔。第三个问题“如果数组不能修改还有 O(1) 空间的解法吗”求和法和异或法都不修改原数组直接回答即可。第四个问题“如果缺失的不止一个数字呢”这道题立刻就不再是 Easy 了会变成“消失的两个数字”这种 Hard 变体。其实解法也不难先用求和算出缺失数字的和再用异或算出缺失数字的异或值两个方程联立就能解出来。但未经训练的人很可能当场卡住所以如果面到这一步说明面试官在有意考察你的应变能力。5. 变体进阶一道题带出一串题5.1 缺失数字的镜像寻找重复数学完缺失数字最该立刻做的是它的“镜像题”——寻找重复数字。一类题目是数组长度 n1元素范围 1 到 n正好有一个数字重复找出它。比如 LeetCode 287。这题和缺失数字的差异只在两点范围从 0 变成 1缺失变成重复。一种很自然的解法是原地置换遍历数组把每个元素放到它应该出现的位置上如果发现某个位置已经被“正确元素”占住了那这个元素就是多余的重复值。另一种更经典的解法是 Floyed 判圈法——把数组看成链表用快慢指针找环入口时间复杂度 O(n)空间 O(1)。这个概念和缺失数字的异或解法是两种完全不同的位运算/数学思路放在一起对比记忆效果比单独刷十道题还好。我刷题时有个很深的体会很多“新题”其实就是“老题”改了半句话。缺失数字范围 0 到 n重复数字范围 1 到 n这两条题在解题模板上是高度互通的——下标和值对应关系的利用一模一样。所以别满足于一道题的 AC而要把相仿的题归档整理。5.2 缺失两个数字的解法如果缺失的不止一个而是两个呢这是《程序员面试金典》里的经典变体思路很有意思。设缺失的两个数是 a 和 b。第一步用求和完整范围的和减去现有数组的和得到 a b S。第二步用异或把 0 到 n1 全部异或一遍再异或所有现有元素得到 a ^ b X。现在有a b Sa ^ b X已知两数之和和两数异或值是可以直接解出 a 和 b 的。一个常见技巧从 X 里找到最低位的 1比如 X 6二进制 110时最低位 1 在第二位说明 a 和 b 在这一位上不同。于是可以把 0 到 n1 的所有数按这一位是 0 还是 1 分成两组分别异或缺失的两个数就被分到了不同的组里各组异或结果就是 a 和 b。代码写出来也不长但推导过程很考验对位运算的理解。这道变体题是面试中从 Easy 跨到 Hard 的经典阶梯值得专门花时间研究。5.3 大数组与流式数据场景再退一步想如果数据量极大无法一次性加载到内存上面的解法还能用吗求和法和异或法都有一个非常好的特性它们是单趟遍历的在线算法不需要随机访问每次只需读一个元素并更新一个变量。这意味着你可以把它用在超大文件或者流式数据管道里只要从头到尾读一遍最终结果自然算出来。但如果你面对的是分布式场景情况又不一样了。比如数据分散在很多台机器上要找一个全局缺失数字这时可以改成“分桶哈希”的思路把 0 到 n 平均切成若干桶统计每桶里实际有多少个元素缺失数字一定落在“数量不对”的那个桶里再对那个桶内部重复这个过程。这套思路本质上就是分治思路比代码更重要。我实际工作中遇到过一个类似的场景系统要校验数据抽样是否有遗漏用的核心数学工具就是求和校验——把数值型的 ID 加起来和预期值对比漏一条记录立刻能发现。可见这道题不是面试后就没用了它在数据校验、完整性检查这类日常工程里真的有应用场景。6. 踩坑实录与刷题建议6.1 求和溢出你以为对的结果未必对我第一次在 Java 里写这道题的最优解直接用了 int 类型的 n * (n 1) / 2结果在 n 稍大一点的测试用例上直接错了。排查了半天赫然发现不是算法逻辑错而是中间计算溢出变成一个莫名其妙的负数再减数组和答案彻底跑偏。这个坑非常隐蔽因为在小规模数据下一切正常只有数据规模大了才暴露。后来我把求和写法全部改成“边加边减”也就是遍历数组的同时 res i - nums[i]再也没出现过问题。这里也提醒各位如果面试官问“数据范围有没有限制”这不是废话而是真的可能影响解法选择。6.2 原地标记的边界陷阱如果你选择了“原地标记法”——比如把数组里出现的值对应的下标位置标成负数最后看哪个下标还是正的——有个边界必须处理数字 n 本身在数组里没有对应下标。因为数组长度是 n下标只能到 n-1遇到值为 n 的元素时会数组越界。常见的规避方法有两种一是先扫描一遍数组如果发现 n 存在就把它临时换成某个已知存在的数比如 0最后再单独处理二是换成“置换到对应位置”的思路遇到 nums[i] 不是 i 就把 nums[i] 换到下标为 nums[i] 的位置上直到当前位置摆对为止。后一种方法在处理“数组元素和下标错位”的一类题时是通解建议专门练熟。另外注意如果你把原数组改成负数标记意味着原数据被破坏题目如果声明“不能修改输入”这种解法直接不能用。解法本身没有对错只有适不适合当前约束。6.3 我的刷题体会说实话这题我第一次做的时候也只想出来排序法和哈希表法看题解发现异或解法时第一反应是“这也能行”第二反应是“这么简单我怎么没想到”。后来把“只出现一次的数字”“寻找重复数”“消失的两个数字”连着刷完才真正理解了异或这套操作背后的统一逻辑——配对抵消。从那以后我的刷题笔记里多了一条规律凡是问题涉及“找没出现的那个”“找多出来的那个”异或永远优先试一下。再分享一个我面试别人时的小观察能完整说出暴力、排序、哈希、求和、异或五种解法的人和只背异或解法的人在后续追问里的表现差距非常明显。前者面对变体能举一反三后者一旦问题从“裸题”变成“数组有序但只能读一次”就直接卡壳。所以我的建议是任何一道 Easy 题先别满足于 AC试着穷尽你能想到的所有思路最好写在纸上。一道题取五种解法比盲目刷五道同类题管用得多。这道“缺失数字”我愿称之为算法面试的试金石它足够简单能让每个人都写出代码又足够深能考察出你是否真正理解数据结构与算法的底层逻辑。把这一道题吃透比你在刷题软件上多完成几十道简单题更有价值。