LeetCode 面试题 17.19. 消失的两个数字
目录
题目描述
题意分析
给定一个数组，它本应包含 1 到 N 的每个整数各一次，但其中恰好有两个数被拿走了，要求把这两个数找出来。由于拿走了两个，数组当前长度是 N - 2，所以 N = nums.length + 2 可以直接推出来，不需要额外参数。
题目最核心的约束写在描述里：要求时间复杂度 $O(N)$、空间复杂度 $O(1)$。这两条同时出现，等于把「排序后扫描」「布尔标记数组」「哈希集合」全部否掉了——前者时间不达标，后两者空间不达标。剩下能在常数空间里把 N 个数聚合成少量变量的手段，只有算术求和与逐位运算这两类。
再看「缺失的是两个而不是一个」。缺一个时，一次聚合就能锁定答案；缺两个时，一次聚合只能得到关于两个未知数的一个方程，必然需要第二个独立的约束才能解开。这就是本题被标为困难而「消失的数字」是简单的根本差别。
边界上：N 最小是 3（数组只剩一个元素），此时缺的两个数与剩下的一个数构成 1、2、3 的一个划分；数组本身无序，不能依赖任何位置信息；两个缺失数一定不相等，因为 1..N 中每个数只出现一次。
解法：按位异或拆分
核心思路
先看暴力：开一个长度 N + 1 的布尔数组，把出现过的数打上标记，再从 1 扫到 N 找出两个没被标记的。时间是 $O(N)$，但空间也是 $O(N)$，直接违反题目要求。用排序代替标记数组能把空间降下来，时间又变成 $O(N \log N)$。瓶颈在于：这些做法都在保留「每个数是否出现」的完整信息，而我们其实只需要两个数字。
第一层观察来自「其余元素恰好成对」。把 1..N 这 N 个理论值和数组里实际存在的 N - 2 个值放在一起看，除了缺失的 a 和 b，其它每个数都恰好出现两次（理论一次、实际一次）。把它们全部异或起来，成对的自动抵消为 0，于是得到第一个方程：$xor = a \oplus b$。
但一个异或和无法拆出两个数——已知 $a \oplus b = 6$，(1,7)、(2,4)、(3,5) 都满足。这就是前面说的「一个方程解两个未知数」的困境。
第二层观察是本题的关键：既然 a ≠ b，那么 $a \oplus b \neq 0$，它的二进制里至少有一个 1。而某一位是 1，恰恰说明 a 和 b 在这一位上取值不同——一个是 0，一个是 1。于是这一位就成了一把天然的分类器：取
lowbit = xor & -xor拿到最低的那个 1，按「该位是 0 还是 1」把 1..N 与数组元素统统分成两堆，a 和 b 必然被分到不同的堆里，而其余成对的元素因为值相同必然进入同一堆、继续两两抵消。由此得到算法的不变量：分组结束后，第一堆的异或和恰好等于 a，第二堆的异或和恰好等于 b。原本的两未知数问题被拆成了两个独立的单未知数问题，每个都退化成「消失的数字」那道简单题。
xor & -xor是取最低位 1 的标准写法，原理是补码取负相当于按位取反再加一，恰好让最低位 1 及其右侧保持不变、左侧全部反转，与原值相与只剩最低位 1。
解题步骤
- 由
n = nums.length + 2还原出完整值域上界。这是后续所有循环范围的依据；题目没有直接给 N，但「恰好少两个」这个条件唯一确定了它。- 先把 1..n 全部异或进 xor，再把数组元素全部异或进同一个 xor。合并成一个变量而不是两个再相异或，是因为异或满足结合律，结果完全相同却少一个变量；这一步结束后 xor 就是 $a \oplus b$。
- 计算
lowbit = xor & -xor。取最低位而不是最高位，纯粹是因为这个表达式最短、无需循环；取任何一个为 1 的位都同样正确。之所以保证 lowbit 不为 0，是因为两个缺失数必不相等，异或和必非零。- 再次同时遍历 1..n 和数组，按
x & lowbit是否为 0 分别异或进 a 或 b。两轮遍历必须用同一个 lowbit、同一套分组规则，否则成对元素会被拆散到两堆导致抵消失效。注意判断写的是== 0而不是== 1，因为 lowbit 可能是 4、8 这样的值，相与的结果是 lowbit 本身而非 1。- 必要时交换 a、b 使输出升序。这一步不影响正确性，只是让返回结果稳定、便于对拍。
以
nums = [1]（N = 3，缺 2 和 3）走一遍。第一步 n = 1 + 2 = 3。第二步先异或 1..3：0 ^ 1 = 1，1 ^ 2 = 3，3 ^ 3 = 0；再异或数组元素 1：0 ^ 1 = 1。所以 xor = 1，正是 2 ^ 3 = 1，符合预期。第三步 lowbit = 1 & -1 = 1，即用二进制最低位（奇偶性）分组。第四步遍历 1..3：i = 1，1 & 1 = 1 非零，b ^= 1 → b = 1；i = 2，2 & 1 = 0，a ^= 2 → a = 2；i = 3，3 & 1 = 1，b ^= 3 → b = 1 ^ 3 = 2。再遍历数组：num = 1，1 & 1 非零，b ^= 1 → b = 2 ^ 1 = 3。此时 a = 2、b = 3。第五步 a < b 无需交换，返回[2, 3]。可以看到值 1 在两轮里各出现一次且都落进 b 组，自行抵消掉了，只留下真正缺失的 3。再用一个 lowbit 不等于 1 的用例验证
nums = [2, 3]（N = 4，缺 1 和 4）：xor 先异或 1..4 得 1 ^ 2 = 3、3 ^ 3 = 0、0 ^ 4 = 4，再异或数组 4 ^ 2 = 6、6 ^ 3 = 5，故 xor = 5 = 1 ^ 4，正确。lowbit = 5 & -5 = 1。遍历 1..4：1 进 b 组（b = 1），2 进 a 组（a = 2），3 进 b 组（b = 1 ^ 3 = 2），4 进 a 组（a = 2 ^ 4 = 6）。遍历数组：2 进 a 组（a = 6 ^ 2 = 4），3 进 b 组（b = 2 ^ 3 = 1）。得到 a = 4、b = 1，交换后返回[1, 4]，与缺失值一致。
代码实现
// 取 xor 的最低位 1，把所有数按该位分成两组，分别异或即可得到 a 和 b。
class Solution {
public int[] missingTwo(int[] nums) {
int n = nums.length + 2;
int xor = 0;
for (int i = 1; i <= n; i++) {
xor ^= i;
}
for (int num : nums) {
xor ^= num;
}
int lowbit = xor & -xor;
int a = 0;
int b = 0;
for (int i = 1; i <= n; i++) {
if ((i & lowbit) == 0) {
a ^= i;
} else {
b ^= i;
}
}
for (int num : nums) {
if ((num & lowbit) == 0) {
a ^= num;
} else {
b ^= num;
}
}
if (a > b) {
int swapValue = a;
a = b;
b = swapValue;
}
return new int[]{a, b};
}
}
// 取 xor 的最低位 1，把所有数按该位分成两组，分别异或即可得到 a 和 b。
func missingTwo(nums []int) []int {
n := len(nums) + 2
xor := 0
for i := 1; i <= n; i++ {
xor ^= i
}
for _, num := range nums {
xor ^= num
}
lowbit := xor & -xor
a, b := 0, 0
for i := 1; i <= n; i++ {
if i&lowbit == 0 {
a ^= i
} else {
b ^= i
}
}
for _, num := range nums {
if num&lowbit == 0 {
a ^= num
} else {
b ^= num
}
}
if a > b {
a, b = b, a
}
return []int{a, b}
}
复杂度分析
- 时间复杂度：$O(n)$，其中 n 为完整值域上界。凭什么？一共四趟线性遍历：两趟求异或和（分别走 1..n 与数组），两趟做分组（同样走 1..n 与数组）。每趟内部只有常数次位运算，没有嵌套循环，总操作数约 4n，常数因子固定。
- 空间复杂度：$O(1)$。凭什么？只用了 n、xor、lowbit、a、b 这五个整型变量和循环下标，没有开辟任何与输入规模相关的数组或哈希结构；返回的长度为 2 的数组是输出本身，不计入额外空间。
关键点总结
- 一个方程不够就再找一个独立约束：两个未知数必须有两个独立信息才能解开。异或和给出第一个，「某一位取值必然相异」给出第二个。遇到「找出两个缺失/落单元素」的题，第一反应就该是「怎么把它们分开」，而不是硬凑公式。
- 异或和的非零位是天然的分类器：$a \oplus b$ 的任意一个 1 位都能把 a 和 b 分到不同组，而任何相等的一对元素永远同组、继续抵消。这个技巧可以迁移到「数组中出现一次的两个数」「两组数据求差异」等一切基于奇偶抵消的问题。
x & -x要能秒答原理：补码下 -x 等于 x 按位取反加一，最低位 1 及右侧不变、左侧全反，相与只留最低位 1。面试时被问到务必讲清补码机制，而不是只说「这是个模板」。- 把「缺失」转化为「成对」：本题的巧妙之处在于主动把理论值域 1..n 和实际数组拼接起来，人为制造出「其余元素各出现两次」的局面。凡是「本应完整但少了几个」的题，都可以这样补全再抵消。
- 求和法是另一条可行路线但更脆弱：用等差数列和减去数组和得到 a + b，再用平方和之差得到 $a^2 + b^2$，联立解一元二次方程也能出答案。它在数学上等价，但平方和会迅速溢出（N 达到 10^5 量级时 $\sum i^2$ 已超过 int），且要处理开方精度，工程上不如异或稳。
- 面试视角：这题标准的对话节奏是——先给哈希/标记数组的 $O(N)$ 空间解法，被要求降到 $O(1)$ 后给出异或和，再自己指出「一个方程解不出两个数」，最后引出按位分组。整条推理链完整讲出来，比直接背出答案的评价高得多。
易错点总结
- 错误写法：把
n写成nums.length而忘记加 2。用例nums = [1]→ n = 1，第一段循环只异或了 1，xor = 1 ^ 1 = 0，lowbit = 0，所有元素都被判进 a 组，返回[0, 0]，答案完全错误。- 错误写法：只异或数组元素、忘记异或 1..n。用例
nums = [2, 3]→ xor = 2 ^ 3 = 1，这是数组内两个数的异或和，与缺失值 1 ^ 4 = 5 毫无关系，后续分组建立在错误的 lowbit 上，返回[3, 2]这类无效结果。- 错误写法：分组判断写成
(x & lowbit) == 1。用例nums = [1, 2]（N = 4，缺 3 和 4，xor = 3 ^ 4 = 7，lowbit = 1）时恰好能过，但换成缺 1 和 3 的用例nums = [2, 4]→ xor = 1 ^ 3 = 2，lowbit = 2，此时x & 2的结果是 0 或 2，永远不等于 1，所有元素都进 a 组，a 变成 1 ^ 3 = 2、b 保持 0，返回[0, 2]。判断必须写成与 0 比较。- 错误写法：分组时只遍历 1..n 而漏掉数组元素（或反之）。用例
nums = [1]→ 只走 1..3 的话 a = 2、b = 1 ^ 3 = 2，返回[2, 2]；数组里的 1 没有参与抵消，b 组残留了不该存在的值。两轮遍历缺一不可。- 错误写法：两轮分组用了不同的 lowbit（例如在第二轮里重新计算）。用例
nums = [2, 3]→ 若第二轮误用xor & (xor - 1)之类的表达式，相同的值 2 在第一轮进 a 组、第二轮进 b 组，抵消关系被打破，两个变量都变成含无关元素的垃圾值。- 错误写法：a、b 初始化为 nums[0] 或 1 而不是 0。用例
nums = [1]→ 若 a 初始化为 1，最终 a = 1 ^ 2 = 3、b = 3，返回[3, 3]；异或的单位元只能是 0，任何非零初值都会作为噪声留在结果里。- 错误写法：用求和法时把平方和存进
int。用例数组长度 10^5（N ≈ 10^5）→ $\sum_{i=1}^{N} i^2$ 约为 $3.3 \times 10^{14}$，远超 int 上限 $2.1 \times 10^9$，溢出后解出的方程根是负数或非整数，返回值毫无意义。异或法则完全没有这个风险。- 错误写法：以为数组已排序而用相邻差值定位缺失。用例
nums = [3, 1]→ 相邻差为 -2，按「差值大于 1 说明中间有缺失」的逻辑会漏判甚至越界；题目从未承诺有序，任何依赖顺序的判据都不成立。- 错误写法：Go 里
lowbit := xor & -xor写成xor & (^xor + 1)但用了无符号类型。若把 xor 声明为uint，取负号在 Go 中对无符号数是编译错误，改用^xor + 1虽可编译，但在与int类型的循环变量相与时会因类型不匹配再次编译失败，浪费大量调试时间。统一用int即可。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 面试题 17.04. 消失的数字 | 简单 | 只缺一个数，一次异或和就是答案，不需要按位分组这一层 |
| 268. 丢失的数字 | 简单 | 值域从 0 开始而非 1，构造理论值域时下标起点不同，容易多算或少算一个 |
| 260. 只出现一次的数字 III | 中等 | 落单元素就在数组内部，无需补全理论值域，分组这一步完全一致 |
| 645. 错误的集合 | 简单 | 一个重复一个缺失，异或和给出两者之差后还需判断谁是重复的，多一步归属判定 |
| 448. 找到所有数组中消失的数字 | 简单 | 缺失个数不定，异或彻底失效，改用原地取负做标记 |
| 41. 缺失的第一个正数 | 困难 | 值域不受数组长度约束，需要原地置换把每个数放回自己的下标位置 |