LeetCode 268简单数学 / 异或
丢失的数字 图解题解
这道题到底在问什么
nums 含 [0, n] 中的 n 个不同整数，恰缺一个，返回缺失的数。要求 O(n) 时间、O(1) 额外空间。
- 输入
- nums=[3,0,1]
- 输出
- 2 （0,1,3 都在，缺 2）
- 输入
- nums=[0,1]
- 输出
- 2 （n=2，缺末尾 2）
最优解：一步一步想明白
- 3记住「下标=该有的、元素=实际有的，缺的那个落单」，下面每一帧都在套它。
- 4异或的魔法：相同的数碰一起就消失，落单的留到最后。
- 5数组下标只到 8，但全集是 0..9。下标 9 没有格子，先把它放进 acc 作初值 = 9。
- 6处理下标 0：把「下标 0」和「这格的值 3」都异或进 acc。配对出现的数会两两抵消，acc 现在 = 10。
- 7处理下标 1：把「下标 1」和「这格的值 0」都异或进 acc。配对出现的数会两两抵消，acc 现在 = 11。
- 8处理下标 2：把「下标 2」和「这格的值 1」都异或进 acc。配对出现的数会两两抵消，acc 现在 = 8。
- 9处理下标 3：把「下标 3」和「这格的值 4」都异或进 acc。配对出现的数会两两抵消，acc 现在 = 15。
- 10处理下标 4：把「下标 4」和「这格的值 6」都异或进 acc。配对出现的数会两两抵消，acc 现在 = 13。
- 11处理下标 5：把「下标 5」和「这格的值 5」都异或进 acc。配对出现的数会两两抵消，acc 现在 = 13。
- 12处理下标 6：把「下标 6」和「这格的值 2」都异或进 acc。配对出现的数会两两抵消，acc 现在 = 9。
- 13处理下标 7：把「下标 7」和「这格的值 8」都异或进 acc。配对出现的数会两两抵消，acc 现在 = 6。
- 14处理下标 8：把「下标 8」和「这格的值 9」都异或进 acc。配对出现的数会两两抵消，acc 现在 = 7。
- 15全部异或完毕。出现两次的数（下标和元素里都有）都成对抵消归零，只剩下那个只在下标里出现、没有对应元素的数：7。
- 16该有的总和减去实际总和，缺口就是那个没加进来的数。
- 17先算「该有的总和」= 0+1+…+9 = 45。再把数组元素一个个加起来求「实际和」，从 0 开始。
- 18加上下标 0 这格的值 3，实际和 sum 累计到 3。
- 19加上下标 1 这格的值 0，实际和 sum 累计到 3。
- 20加上下标 2 这格的值 1，实际和 sum 累计到 4。
- 21加上下标 3 这格的值 4，实际和 sum 累计到 8。
- 22加上下标 4 这格的值 6，实际和 sum 累计到 14。
- 23加上下标 5 这格的值 5，实际和 sum 累计到 19。
- 24加上下标 6 这格的值 2，实际和 sum 累计到 21。
- 25加上下标 7 这格的值 8，实际和 sum 累计到 29。
- 26加上下标 8 这格的值 9，实际和 sum 累计到 38。
- 27实际和加完是 38。该有的总和 45 减去它 = 7，正是那个没被加进来的缺失数。两种解法答案一致：7。
⚠️ 容易写错的地方
✗ 错：acc 初值写成 0
✓ 对：acc 初值 = n（或循环到 i<=n 把下标 n 也异或）
下标范围是 0..n 共 n+1 个，数组只有下标 0..n-1，漏掉下标 n 会算错
✗ 错：求和法用 int 存 sum，n 很大时溢出
✓ 对：用 long / 或干脆用异或法
n*(n+1)/2 在 n 达数万时可能超出 int 上限；异或法不受此限
✗ 错：以为数组必须先排序
✓ 对：无需排序，一遍异或/求和即可
异或和求和都与顺序无关，排序是 O(n log n) 的多余开销
完整代码（Python / C++ / Java）
Python
def missingNumber(nums):
n = len(nums)
acc = n # 先放下标 n
for i, v in enumerate(nums):
acc ^= i ^ v # 异或下标和元素
return acc # 成对抵消，剩缺失数
# 求和法（等差和 - 实际和）：
# return n * (n + 1) // 2 - sum(nums)C++
int missingNumber(vector<int>& nums){
int n = nums.size();
int acc = n; // 先放下标 n
for(int i = 0; i < n; i++)
acc ^= i ^ nums[i]; // 异或下标和元素
return acc; // 剩下的就是缺失数
// 求和法: return n*(n+1)/2 - accumulate(...);
}Java
public int missingNumber(int[] nums) {
int n = nums.length;
int acc = n; // 先放下标 n
for (int i = 0; i < n; i++) {
acc ^= i ^ nums[i]; // 异或下标和元素
}
return acc; // 成对抵消，剩缺失数
// 求和法: int s=n*(n+1)/2; for(int v:nums)s-=v; return s;复杂度
时间
O(n)
每个元素只扫一遍，异或或累加一次
空间
O(1)
只用 acc/sum 一个变量，原地
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 丢失的数字 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
异或法和求和法，面试更推荐哪个？+
异或法。两者都是 O(n)/O(1)，但求和法的中间值 n*(n+1)/2 在 n 很大时可能整数溢出，需要用更宽的类型；异或法全程在位级别操作，不存在溢出问题，更稳健，也更能体现对位运算的理解。
如果缺了两个数怎么办？+
全员异或得到的是「两个缺失数的异或值」。可以用这个异或值里任意一个为 1 的二进制位，把所有数分成两组（该位为 0 / 为 1），两个缺失数必然落在不同组，组内各自异或即可分别得到它们。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 丢失的数字 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。