LeetCode 268简单数学 / 异或
丢失的数字 图解题解
这道题到底在问什么
长度 n 的数组包含 0..n 中缺一个数，找出缺失值。
- nums
- [3,0,1]
- 输出
- 2
最优解：一步一步想明白
⚠️ 容易写错的地方
✗ 错：范围只加到 n-1
✓ 对：完整范围是 0..n，一共 n+1 个数
缺的可能正好是 n
✗ 错：大 n 求和溢出
✓ 对：改用异或法，或边加边减
n 很大时 n(n+1)/2 可能超出 int；异或法天然不溢出。
✗ 错：变量名和动画不一致
✓ 对：代码变量沿用动画里的核心名字
学习时最怕脑内维护两套概念
完整代码（Python / C++ / Java）
Python
class Solution:
def missingNumber(self, nums):
n = len(nums)
return n * (n + 1) // 2 - sum(nums) # 完整和 - 实际和C++
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int total = n * (n + 1) / 2; // 完整和
for (int x : nums) total -= x; // 减去实际和
return total;
}
};Java
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int total = n * (n + 1) / 2; // 完整和
for (int x : nums) total -= x; // 减去实际和
return total;
}
}套路模板 · 求和差 / 异或
# 缺失数字骨架（两种 O(1) 空间法）
# 法1 求和差：
return n*(n+1)//2 - sum(nums)
# 法2 异或(不会溢出)：
x = 0
for i in range(n+1): x ^= i
for v in nums: x ^= v
return x复杂度
时间复杂度
O(n)
遍历数组一次求和（或一遍异或）
空间复杂度
O(1)
无额外结构，只用几个整型累加
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 丢失的数字 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
异或和求和差怎么选？+
都 O(n)、O(1)。异或不会溢出更安全；求和差更直观但大数可能溢出。
为什么异或能找缺失数？+
把 0..n 和数组一起异或，每个出现的数恰好两次(成对消失)，只有缺失的在 0..n 出现一次、留下。
和「只出现一次 LC136」的联系？+
同一招异或消对；本题把完整序列 0..n 和数组一起异或，缺的那个落单。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。