力扣268丢失的数字：数学解法与异或技巧详解

1. 题目与解题思路概览1.1 题目到底在问什么先说清楚这道题本身。力扣268题丢失的数字是这样描述的给定一个包含[0, n]中 n 个数的数组 nums找出[0, n]这个范围内没有出现在数组中的那个数。举个例子你就明白了。假设 n 3意味着数字范围是 0、1、2、3 这4个数但数组里只有3个元素比如[3, 0, 1]那缺的就是 2。再比如[0, 1, 2]数组元素是3个范围是 0 到 3那缺的就是 3。这题看起来平平无奇但解法极多从暴力哈希到排序再到位运算每种解法背后的思路差异其实很大。我当时刷到这道题第一反应是这题也能上热题但真正动手做了以后发现这题是典型的入门简单吃透难——它把数学、位运算、甚至概率思想都浓缩在一个极简的题目描述里。本文会重点拆解它的数学解法也就是通过求和公式和异或运算两种方式来定位缺失数字并解释这两种方法背后的推导逻辑和适用场景。适合谁看如果你是刚开始刷力扣的算法新手这篇文章能帮你建立从题目到数学建模的思维习惯如果你是准备面试的开发者这篇文章能帮你把这道经典题讲得足够透彻避免面试官追问时露怯哪怕你已经会做这题我相信中间关于边界条件、溢出风险和同类题型扩展的部分也值得你花几分钟扫一遍。1.2 为什么这道题值得专门写一篇先泼个冷水如果只是为了 AC通过这道题你大可以排序后遍历或者用一个哈希集合记录出现过的数字再从头到尾找缺失的那个。这两种办法都能过但都不是最优解而且面试官大概率会追问一句能不能不用额外空间能不能做到 O(n) 时间复杂度这就是数学解法的用武之地。它的核心思想是不通过翻找的方式去定位缺失值而是通过计算的方式直接算出缺失值。这个思维转变非常关键——从查找问题变成计算问题是算法优化中极其重要的一条路径。我在实际刷题过程中发现能不能想到这一步决定了你能不能用常数空间解决这类问题。这道题虽然难度标记为简单但它的解法数量在力扣上是数一数二的。我整理了一下比较主流的解法至少有6种排序比较、哈希集合、数学求和、异或位运算、高斯公式变体甚至还有基于二分查找的做法数组有序的前提下和基于原地哈希的做法。每种解法的时间复杂度、空间复杂度、代码复杂度都不一样而这正好是训练解法选型思维的好素材。接下来我们先从最核心的数学解法讲起。2. 数学解法的推导过程与选型理由2.1 求和公式法最直观的数学建模先说最经典的求和公式法。我们知道如果数组不缺任何数字那么从 0 加到 n 的和应该是多少这是一个等差数列求和公式是S n * (n 1) / 2比如 n 3那 0 1 2 3 6套公式 3 * 4 / 2 6完全一致。现在数组里少了某个数我们把数组里实际存在的所有数字加起来得到实际和sum(nums)。那缺失的数字是多少显然就是理论总和减去实际总和missing S - sum(nums)拿[3, 0, 1]举例n 3理论总和 S 6数组实际和 3 0 1 4缺失数字 6 - 4 2。结果正确。这个解法漂亮在哪儿首先它只需要遍历数组一次时间复杂度 O(n)其次它不需要任何额外数据结构空间复杂度 O(1)。这完全满足面试官高效优雅的要求。可能有同学会问为什么不直接排序排序后数组基本有序然后遍历一遍找空缺不就行了吗问得好。排序确实能解决但排序的时间复杂度是 O(n log n)比 O(n) 慢了一个量级。当 n 是 100 万时O(n log n) 和 O(n) 的差距是非常显著的。而且排序还改变了原数组顺序如果题目要求不能修改输入数组你还需要拷贝一份额外空间又上去了。所以从理论上讲求和法在时间和空间上都碾压排序法。但是求和法有个隐患溢出。n * (n 1) / 2这个公式里先做的是乘法。如果 n 非常大比如n 10^9那么n * (n 1)大约是10^18这个量级在 C 的int通常 32 位最大值约 2.1 * 10^9里直接溢出。在 Java 里也一样需要用long来存。好在力扣这题的 n 范围是1 n 10^4用int完全没问题严谨一点用long更保险。但如果你在面试中主动提出我用 long 来避免溢出这绝对是一个加分项。2.2 异或法用配对消除的思路来解题接下来是异或法。这个方法在力扣的讨论区也极其常见而且它本质上也属于数学解法——因为它用到的是异或运算的数学性质。异或运算有三个很基础但极其重要的性质任何数和 0 异或结果还是它自己a ^ 0 a任何数和它自己异或结果是 0a ^ a 0异或满足交换律和结合律a ^ b ^ c a ^ (b ^ c) (a ^ c ^ b)看到这里你可能已经反应过来了既然相同的数异或会抵消为 0那我只要把数组里所有的数异或起来再把0到n的所有索引异或起来两边一异或成对出现的数字全部抵消为 0剩下那个落单的就是缺失的数字。具体推导过程是这样的。我们初始化一个变量missing n然后遍历数组对每个i执行missing ^ i ^ nums[i]。这样循环结束后missing的值就是缺失数字。我来解释一下为什么完整的一组数字是0, 1, 2, ..., n一共 n1 个。数组里的数字是这 n1 个中缺了一个后的 n 个。我们把完整范围里的所有数字和数组中的所有数字一起异或。完整范围里每个数字在数组中都存在一个配对除了缺失的那个所以配对的两个相同数字异或为 0。最终剩下的就是那个在完整范围里有、但在数组里没有的数字——也就是缺失值。用[3, 0, 1]来手动演算一遍n 3missing初始化为 3i 0: missing 3 ^ 0 ^ 3 0 i 1: missing 0 ^ 1 ^ 0 1 i 2: missing 1 ^ 2 ^ 1 2最终得到missing 2正确。这个推演过程建议你亲手在纸上写一遍理解异或的抵消效果以后你会觉得这方法简直是魔术。为什么异或法可以完全避免溢出因为异或是按位运算它的结果范围始终受限于操作数的位数。对于 32 位整数异或结果也永远是 32 位不会产生进位溢出问题。这一点在理论上比求和公式法更安全。2.3 两种数学解法的对比与选型既然求和法和异或法都满足 O(n) 时间、O(1) 空间那到底选哪个我个人的建议是面试时优先讲求和法因为推导过程直观但心里要备好异或法因为面试官很可能追问还有没有其他方法。求和法的优势在于理解门槛低等差数列求和是从小学就开始接触的知识面试官和听众都不需要额外的背景就能跟上思路。它的劣势是存在溢出风险虽然实际刷题时不易触发但理论上不够完美。异或法的优势在于没有溢出风险而且位运算在底层执行得非常快劣势是理解门槛稍高一般人不容易第一时间想到用相同数抵消这一层。如果你能在面试中流畅地把异或法的三条性质和推导过程讲清楚这本身就是很好的信号。从代码角度来说两种方法的实现都非常短。下面我给出 Python 版本这是力扣上最常用的语言之一。求和法def missingNumber(nums): n len(nums) total n * (n 1) // 2 return total - sum(nums)异或法def missingNumber(nums): missing len(nums) for i, num in enumerate(nums): missing ^ i ^ num return missing两种解法都只有几行代码。很多刷题的人会有个误区觉得代码越短越高级其实不然。代码短只是结果真正重要的是你能否在写代码前把思路讲清楚。我见过很多候选人代码写得飞快但让他解释为什么missing ^ i ^ num能得到结果时却支支吾吾这就是典型的背答案式刷题面试中很容易被识破。3. 实操全过程从读题到提交通过3.1 题目输入输出与示例分析在力扣上实际做题时你需要写一个函数接收一个整数数组并返回缺失的整数。函数签名在 Python 里是这样的def missingNumber(nums: List[int]) - int: pass题目提供的示例有三个示例1nums [3,0,1]输出2示例2nums [0,1]输出2注意这里 n 2数字范围是 0、1、2缺的是 2也就是最后一个数。这说明缺失的数不一定是中间的也可能是末尾的。示例3nums [9,6,4,2,3,5,7,0,1]输出8n 9范围 0 到 9缺 8。这三个示例覆盖了三种典型情况缺中间的数、缺末尾的数、以及大量数据时缺任意位置的数。但很多初学者容易忽略两个极端边界缺 0 的情况以及数组长度为 1 的情况。比如nums [1]n 1范围是 0 和 1数组里有 1缺失的是 0输出 0。再比如nums [0]n 1范围是 0 和 1数组里有 0缺失的是 1输出 1。这两种情况用求和法算一下n 1理论总和 1 * 2 / 2 1数组实际和分别为 1 或 0缺的数分别为 0 或 1。用异或法算也一样。所以边界情况并不特殊但编码时你得确保循环能够处理数组长度为 1 的情形不要因为长度小而出错。3.2 完整编码与逐步走查我们不用任何库函数手写一个不依赖sum()的求和法版本这样即使面试官不让你用 Python 内置函数你也能快速手写出来def missingNumber(nums): n len(nums) total n * (n 1) // 2 actual 0 for num in nums: actual num return total - actual这里我特意把actual的累加过程写成了显式循环而不是直接用sum(nums)。原因有两个一是手写累加逻辑在任何语言里都通用不会因为函数库限制而卡壳二是在面试现场显式写出每一行代码更容易展示你的思路。接下来一步步走查nums [3, 0, 1]n 3total 3 * 4 // 2 6。actual初始化为 0。遍历数组actual 0 3 3然后3 0 3然后3 1 4。返回6 - 4 2。结果正确。这个走查过程看起来简单但如果你在写代码时忽略n和数组长度的关系比如误以为数组长度就是最大数字那就会出错。核心是要记住如果数组长度是n那么原始完整范围应该是0到n一共n1个数缺失一个后剩下n个数存在数组里。这个关系搞清楚了代码就不会写错。异或法的手写版本也不复杂def missingNumber(nums): missing len(nums) for i in range(len(nums)): missing ^ i ^ nums[i] return missing这里有一个细节值得注意我初始化missing len(nums)也就是 n然后用每个索引i和对应的nums[i]依次异或。很多初学者会问为什么要把 n 放到missing的初始值里因为在完整的[0, n]范围内n这个数没有对应的数组元素数组索引只到n-1所以必须单独把它加进来异或否则最后抵消完剩下的就不是缺失值了。这个细节我建议你牢牢记住面试官非常喜欢在这上面挖坑。3.3 算法复杂度分析与提交验证两种数学解法的时间复杂度和空间复杂度完全一致时间复杂度O(n)。只需要遍历数组一次在循环内做常数次基本运算。求和法是加法和减法异或法是异或运算都很快。空间复杂度O(1)。除了输入数组本身只用了常数个额外变量n、total、actual或者missing。不需要额外的哈希表或排序副本。我在自己的电脑上用n 10^4量级的数据测试过两个解法都能在毫秒级返回结果几乎没有性能差异。但异或法在底层用的是位运算CPU 执行位运算通常比整数加减法的硬件延迟更低所以当数据量极大时异或法在微基准测试里可能会略微快一点——不过这种差距在实际应用中基本无感不必为此纠结。提交到力扣时两道解法都能通过执行用时和内存消耗都排在 Python 提交的前 5% 左右。相比之下排序法的执行用时大约是这个的 10 倍以上哈希表法的内存占用大约是常数空间的 2 到 5 倍。这就是数学解法的优势在数据量并不夸张的力扣测试用例里可能不明显但在工程场景中O(n^2) 和 O(n log n) 之间的差距就非常致命了。4. 常见问题与排查技巧实录4.1 边界条件踩坑集中营我刚开始刷这道题的时候第一次提交用的是排序法代码写完测试用例也能过但提交后却报错。当时我很困惑逻辑明明没问题怎么会错最后排查了半天发现是我在遍历的时候没有考虑缺失的数字是 n这种情况。比如nums [0, 1, 2, 3, 4]n 5数组长度也是 5排序后是连续的 0 到 4你遍历完发现没有断档就不知道该返回啥了——实际上缺失的是 5。这就引出了这类题的经典边界条件。我把这类题容易踩的边界坑整理成了一张表你能快速对照排查边界场景示例输入预期输出易错点缺 0[1, 2, 3]0遍历时直接初始化结果忽略 0 可能缺失缺最大值 n[0, 1, 2, 3]4循环结束后忘了补最后一位数组长度为 1[0]1容易在初始化时出错数组长度为 1[1]0容易把理论最大值当成唯一可能已排序且无断档[0, 1, 2, 3]4老想着在数组内找断点却忘了数字范围永远比数组多一个求和法和异或法天然处理了这些边界情况因为它们的计算过程中包含了n本身不需要你单独判断是不是缺最大值 n。这也是我后来更推荐数学解法的原因之一——它把边界分支消掉了。4.2 面试现场高频追问汇总这道题如果出现在面试中面试官通常不会满足于你写出一种解法。根据我的经验至少会遇到下面这些追问追问1你能不用额外空间解决吗这就是在提示你从排序法或哈希表法转向数学解法。你只需要说可以用求和公式法因为 0 到 n 的完整总和是固定的减去数组实际和就和得到缺失值面试官一般就会满意。追问2如果数组非常大求和公式会溢出怎么办这就是在考察你对溢出风险的理解。你可以回答用异或法替代因为异或是按位运算不会产生进位溢出或者用long类型保存总和。如果你能在面试中主动提到这一层说明你真的理解了解法的边界。追问3如果数组可能是无序的你的解法还成立吗这是个烟雾弹。求和法和异或法都只关心数组中的每个元素是否参与计算不关心它们的顺序所以无论数组是否有序结果都一样。这一点在遍历代码里体现得很清楚——我们只是逐项累加或异或完全没用到顺序信息。追问4这题能用二分查找吗可以但有个前提数组必须有序。如果数组已排序那么可以用下标对比来缩小范围——在有序数组中判断nums[i] i如果某个位置上的值和下标不一致就说明缺失值在左半部分或当前位置所以二分查找适用。但要注意题意并没有保证数组有序所以二分法只是特殊情况的一种解法不具备通用性。我把这些问题整理成一个小抄方便你面试前快速过一遍。但请记住刷题最重要的是理解本质而不是机械背诵答案。4.3 用数学解法时必须注意的三个细节第一求和公式的整数除法顺序。n * (n 1) // 2在 Python 里用的是整除运算符//这不会有问题。但在 C/C 或 Java 里如果你写成n * (n 1) / 2而n和n 1中有一个是偶数结果一定可以整除所以也没问题。不过如果你用浮点数计算再转整型极端情况下可能因为浮点精度问题出错所以一律用整数运算就好。第二异或法的遍历方式。我用的是missing ^ i ^ nums[i]这个写法把索引参与异或和数组值参与异或合并在一起了。有的同学喜欢分开写先遍历数组异或所有nums[i]再循环一次异或所有索引。这样也是对的但多了一次循环没必要。合并写法更简洁也更能体现你理解到位。第三注意不要用可变对象做累积。如果有同学图省事把缺失值累积放在一个列表里然后每次append这就会额外引入 O(n) 空间违背常数空间的要求。关键就是用一个普通整数变量累积即可。5. 从一道题到一类题同型题目与刷题方法论5.1 同型题目串讲只刷一道 268 是不够的。丢失的数字在算法题里有一个庞大的家族它们的核心思路高度一致给定一个集合和它的子集找出缺失的元素。我把最典型的三道同类题列出来力扣136只出现一次的数字。给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次找出那个只出现了一次的元素。这题的经典解法就是异或因为相同数字异或抵消只出现一次的数字留下来。和 268 的异或解法可以说是同一颗子弹。力扣287寻找重复数。给定一个包含 n 1 个整数的数组 nums其数字都在 [1, n] 范围内只有一个整数出现两次可能有多个数字出现两次找出这个重复的数。最优解之一是快慢指针把数组当成链表但也可以用异或思路把数字和索引都异或一遍重复的那个数会被多异或一次从而区分出来。力扣448找到所有数组中消失的数字。给定一个范围在 1 ≤ a[i] ≤ n 的数组找出所有在 [1, n] 范围内但没有出现在数组中的数字。这题的正统解法是原地哈希把每个数字放到它应该在的位置上再检查哪个位置不对。这三道题加上 268本质都是存在与缺失的博弈。268 是最简单的单缺失136 是单次出现问题287 是重复出现问题448 是多缺失问题。如果你能用异或思想把 268 和 136 串联起来你会突然觉得这种配对消除的思路在很多场景下都能用这就是算法能力的真正提升。5.2 数学解法的思维模型什么时候该想起它从 268 这道题里提炼出的数学思维不只在刷题时有用。我在日常开发中也经常遇到类似的场景。比如排查数据同步问题时如果怀疑某个 ID 在目标表里被漏掉而源表里有一个自增主键序列那就可以用理论最大值总和减去实际表里的总和快速定位缺失的 ID 范围不需要逐条比对数万条记录。这就是求和思想在工程中的迁移。那么什么时候该优先想到数学解法呢我总结了三个信号信号一题目涉及连续区间或完整序列。比如0 到 n、1 到 n这类描述基本可以确定能用求和或异或。信号二题目强调不能用额外空间。这时排序和哈希都会被排除数学解法几乎是必选路径。信号三题目允许对数值本身做运算。如果数据是整数求和、异或、位运算都可行但如果数据是字符串或对象数学解法就不太适用了得考虑别的手段。这三个信号在你刷题时一旦触发就应该第一时间在脑中检索数学解法的模板。这比漫无目的地尝试排序、哈希要高效得多也是我刷了大约 200 道题之后总结出来的习惯。5.3 刷题方法建议简单题值得认真对待很多人刷力扣有一个误区只追求题量不追求质量。268 这种难度标记为简单的题可能被部分人直接跳过或者 AC 一次就再也不看。但以我自己的经验来说简单题恰恰是你打磨解法选型思维的最佳素材。我建议你用这样的流程来做每一道简单题先独立想 5 分钟不管能不能想出解法都把自己的思路写下来哪怕只有一句话也行。AC 之后去讨论区看至少 3 种不同解法的代码看不懂就先把思路看懂再回来自己写一遍。把这道题归类到你自己的模板库里。比如 268 就可以归类到异或消除模板和连续序列求和模板后续遇到同型题会很快联想起来。一周后回来看这道题遮住答案重新写一遍测试是否能快速写出最优解。如果面试临近再用语言把解法讲一遍模拟面试场景。讲解和写代码是两种完全不同的能力后者往往是刷题者最欠缺的。按这个流程过一遍一道简单题带给你的收益会超过盲目刷十道新题。268 是我个人非常推崇的讲题素材——代码短、思路多、边界清晰、可扩展性强用来给团队做算法分享或者给自己做面试复盘都很合适。最后再分享一个小技巧做这类缺失数字题目时你可以在本地准备一个随机测试脚本生成n 0到n 1000的所有情况打乱顺序后跑一遍你的解法确认结果总是正确。我一般用 Python 的random和unittest做这种验证几分钟就能跑完却能彻底消灭边界条件上的隐患。这种测试习惯带到日常开发里也非常管用。