268. 丢失的数字
难度：简单 | 主题：数学 / 位运算 / 哈希表
题目
给定一个包含 [0, n] 中 n 个数的数组 nums，找出这个范围内没有出现在数组中的那个数。
示例
nums = [3, 0, 1] → 2
解释：n=3，完整范围 [0,1,2,3] 中缺失 2
思路
先讲个故事：幼儿园点名
老师拿着花名册（0 号到 n 号）点名，发现 少了一个人。但花名册上没标谁是几号——只能自己算。
你怎么快速找到那个没来的小朋友？
引导式推导：三种思路，两种最优
方法一：数学法——高斯求和
完整范围 [0, n] 的总和 = n(n+1)/2，减去数组实际总和，差值就是缺失的数。
n = len(nums) # n=3, 范围 [0,3] 共 4 个数
expected = 3*4//2 = 6 # 0+1+2+3 = 6
actual = 3+0+1 = 4 # 数组里有的
missing = 6 - 4 = 2 # ✓
方法二：位运算法——异或抵消
利用 a ^ a = 0：把 [0, n] 所有数和数组里所有数一起异或，出现两次的抵消为 0，只剩缺失的数。
范围: 0 ^ 1 ^ 2 ^ 3 = 此范围异或值
数组: ^ 3 ^ 0 ^ 1 = 异或上数组中所有数
结果: (0^0) ^ (1^1) ^ 2 ^ (3^3) = 0 ^ 0 ^ 2 ^ 0 = 2
graph LR A["初始化 xor = n"] --> B["遍历 i, nums[i]"] B --> C["xor ^= i ^ nums[i]"] C --> D["出现两次的抵消<br/>只剩缺失的数"] D --> E["返回 xor"]
多解法对比
| 做法 | 时间 | 空间 | 特点 |
|---|---|---|---|
| 数学法 | O(n) | O(1) | 最直观，一行代码 |
| 位运算 | O(n) | O(1) | 酷炫，不怕溢出 |
| 排序 + 下标 | O(n log n) | O(log n) | 最笨但可靠 |
| 哈希集合 | O(n) | O(n) | 空间换时间 |
代码
def missingNumber(self, nums):
n = len(nums)
return n * (n + 1) // 2 - sum(nums) # 期望总和 - 实际总和
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(n) | sum(nums) 需遍历 |
| 空间 | O(1) | 常数变量 |
实战考量
延伸思考
Q：为什么数学法要注意用 // 而不是 /？
A：Python 中 / 返回浮点数，大 n 时可能丢失精度。// 是整数除法，精确无误。
Q：异或法的原理是什么？能一步步拆解吗？
A：xor 初始化为 n（因为 n 在范围里但不在数组下标范围里）。然后遍历 (i, num)，xor ^= i ^ num。下标 i 和数值 num 完美配对——出现两次的抵消为零，剩下缺失的数。
Q：如果改成 [1, n] 而不是 [0, n] 呢？
A：数学法：(1+n)*n/2 - sum(nums)。异或法：xor 初始化为 0，遍历时 xor ^= (i+1) ^ num。
Q：如果缺失两个数呢？
A：先算总和差和平方和差 → 解方程组。或者异或后得到 a ^ b，根据最低不同位分成两组分别异或。
Q：跟 136只出现一次的数字 有什么区别？
A：那题是找数组中出现一次的数（其他都出现两次），这题是缺失的数。但核心思想相通——都是利用异或 a ^ a = 0 的抵消性质。
易错点
-
高斯求和用
//不是/ -
数组长度 n 对应范围
[0, n]共 n+1 个数 -
异或法记得
xor初始值 =len(nums)（不是 0） -
不要惯性思维走排序/哈希——有更优解法
生活类比
数学法 → 老师查人数
老师知道花名册上应该是 0 到 n 号，心算总人数，然后数一遍教室里实际的人数，差就是没来的。
不翻名单、不排序——脑子算总和就行。
相关题目
| 题目 | 关系 |
|---|---|
| 136只出现一次的数字 | 位运算同族，都是利用异或找唯一元素 |
| 41缺失的第一个正数 | 原地哈希进阶版，O(1) 空间找缺失的最小正数 |
→ 返回题单：LeetCode学习路线图 > 一、数组与哈希（含双指针、矩阵）
速记卡（面试闪卡）
Q1：一句话讲清「268. 丢失的数字」到底是什么？
A：在 [0,n] 中 n 个数缺一个，找出没出现的那个数。
Q2：题目 —— 怎么理解？
A：像老师点名少一人：给 n 个数覆盖 [0,n] 范围却缺一个，找出缺席的那位。比如 [3,0,1] 缺 2，n=3 完整范围是 0~3 共四个数。
Q3：思路 —— 怎么理解？
A：两种最优解法：数学法（高斯求和）算期望总和 n(n+1)/2 减实际和得差值；位运算（异或抵消）把 0~n 与数组所有数一起异或，出现两次的抵消为 0，只剩缺失数。
Q4：代码 —— 怎么理解？
A：一行解题：return n*(n+1)//2 - sum(nums)。异或版则 xor 初值设为 n，遍历时 xor ^= i ^ nums[i]，最后剩下的就是答案，不怕大数溢出。
Q5：复杂度与实战考量 —— 怎么理解？
A：时间 O(n)（遍历求和/异或），空间 O(1)（常数变量）。注意用 // 整数除防浮点精度丢失；异或法 xor 初值是 len(nums) 不是 0；别惯性走排序/哈希，有更优解。
Q6：核心速记主线有哪些？
-
数学法：期望和减实际和
-
异或法：抵消成对得缺失
-
时间 O(n)、空间 O(1)
-
易错：// 整除、xor 初值=n
口诀
A：丢失数字别乱找，高斯求和差一出；
异或抵消成对消，剩下便是缺席徒；
时间 On 空间一，整数除法莫糊涂；
xor 初值要设 n，一遍写对稳如故。