LeetCode 面试题 17.04. 消失的数字

2026-03-28 HGNULB 约 9 分钟

文章信息 3 个分类 5 个标签

分类

题目描述

✅ 面试题 17.04. 消失的数字

题意分析

数组 nums 里装着 0 到 n 这 n + 1 个整数中的 n 个，恰好少了一个，要求把少掉的那个找出来。数组本身是乱序的，下标和值之间没有任何现成的对应关系。

约束里透露了三个强信号。第一，值域是封闭且已知的 [0, n]，n 就等于数组长度，这意味着「应该有哪些数」不需要额外信息就能算出来，问题从「查找」退化成了「已知全集减去现有集合」。第二，题目明确要求线性时间、常数额外空间，这直接封死了排序（$O(n\log n)$）和开辅助数组或哈希集合（$O(n)$ 空间）两条路。第三，缺失的只有一个，不是两个也不是任意个，说明答案可以被压缩进一个标量里，不需要维护任何集合。

边界上要照顾三种情况：nums 为空时值域是 [0, 0]，答案是 0；缺的正好是 0（数组是 1..n）；缺的正好是 n（数组是 0..n-1）。后两种是最容易被「只看数组内部」的写法漏掉的，因为缺失值落在数组值域的两端而不是中间。

还有一个隐藏的坑：n 可以到 $10^5$ 量级，如果打算用「全集之和减去数组之和」这条路，两个和都在 $10^{10}$ 量级之外吗？$n(n+1)/2$ 在 $n = 10^5$ 时约 $5 \times 10^9$，已经超过 int 上限，必须用 long 或换一条不做加法的路。

解法：哈希表统计状态

核心思路

最朴素的写法是：开一个长度为 n + 1 的布尔数组（或哈希集合）当计数器，把 nums 里出现过的数逐个打上标记，再从 0 扫到 n 找那个没被标记的。这个思路完全正确，时间也是 $O(n)$，但它需要 $O(n)$ 的额外空间，撞上了题目的常数空间要求。

瓶颈出在哪里？出在我们记录了太多信息。布尔数组精确地记住了「每一个数分别出没出现」，可我们真正需要的只有一句话：「哪个数出现了 0 次」。既然除了答案之外的每个数都恰好出现 1 次（一次在 nums 里、一次在 0..n 这个全集里，合起来 2 次），而答案只出现 1 次（只在全集里），那么整个问题就变成了在一堆「出现两次」的数里找那个「出现一次」的数。

这个观察一旦成立，就不必再逐个数地记账了——只需要一个能把「出现两次」自动抵消掉的累积运算。异或恰好是这样的运算：x ^ x = 0（成对抵消）、x ^ 0 = x（单身留下），并且满足交换律和结合律（所以元素来的顺序无所谓，乱序数组照样能用）。

于是维护一个标量 answer，把全集 0, 1, ..., n 和数组元素 nums[0..n-1] 全部异或到一起。循环不变量是：扫描到第 i 步时，answer 等于「前 i 个下标 + 数字 n + 前 i 个数组元素」这堆数的异或值；所有已经凑成对的数都已经抵消为 0，answer 里只残留尚未配对的部分。扫描结束时全部配对完成，唯一没有搭档的就是缺失值，answer 就是答案。

实现上有个小技巧：全集是 0..n 共 n + 1 个数，而数组只有 n 个元素，两者长度对不齐。把 answer 的初值直接取成 n，剩下的 0..n-1 正好和下标 i 一一对应，循环里一次 answer ^= i ^ nums[i] 就把两边都吃掉了，一趟扫完，不需要两个循环。

解题步骤

令 n = nums.length，把 answer 初始化为 n。这不是随手取的初值：全集 0..n 比数组多出一个元素 n，先把它记在账上，剩下的 0..n-1 就能靠下标补齐，从而把两趟遍历压成一趟。写 answer = 0 而不额外补 n，会漏掉全集的最后一项。

单层遍历 i 从 0 到 n - 1，执行 answer ^= i ^ nums[i]。i 贡献的是全集里的数，nums[i] 贡献的是实际存在的数，两者在同一次迭代里进账，谁先谁后不影响结果——异或满足交换律和结合律，这正是无需先排序的原因。

循环结束直接返回 answer。不需要任何后处理，也不需要判断 answer 是否合法：全集与数组的差集必然只有一个元素，题目已经保证了这一点。

不要写任何针对空数组、缺 0、缺 n 的特判。这三种情况会自然落进主逻辑：空数组时循环一次都不进，返回初值 n = 0，正确；缺 0 或缺 n 时它们同样只出现一次，照样是唯一的「单身汉」。特判越少，能出错的地方越少，这也是好实现的标志。

以 nums = [3, 0, 1] 走一遍。此时 n = 3，全集是 {0, 1, 2, 3}，缺的是 2。

初始：answer = 3（先把全集里多出来的 n = 3 记上）。
i = 0：answer ^= 0 ^ nums[0] = 0 ^ 3 = 3，得 answer = 3 ^ 3 = 0。全集的 3 和数组里的 3 在这一步就配对抵消了。
i = 1：answer ^= 1 ^ nums[1] = 1 ^ 0 = 1，得 answer = 0 ^ 1 = 1。此刻账上残留 1（来自下标）和 0（来自数组），它们各自的搭档还没出现。
i = 2：answer ^= 2 ^ nums[2] = 2 ^ 1 = 3，得 answer = 1 ^ 3 = 2。下标贡献的 1 和数组里的 1 配对抵消，下标贡献的 0（第一轮那次）和数组里的 0 也早已抵消，只剩下第三轮下标贡献的 2 无人认领。
循环结束，返回 answer = 2，正是缺失的数字。

再看一个缺失值落在端点的例子 nums = [1, 2]：n = 2，answer 初值为 2；i = 0 时 answer ^= 0 ^ 1 = 1 得 3；i = 1 时 answer ^= 1 ^ 2 = 3 得 0。返回 0，正确——不需要为「缺的是 0」写任何特殊分支。

代码实现

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        // 初值取 n，补上全集 0..n 相对下标 0..n-1 多出来的那一项。
        int answer = n;

        for (int i = 0; i < n; ++i) {
            answer ^= i ^ nums[i];
        }

        return answer;
    }
}

func missingNumber(nums []int) int {
    n := len(nums)
    // 初值取 n，补上全集 0..n 相对下标 0..n-1 多出来的那一项。
    answer := n

    for i, v := range nums {
        answer ^= i ^ v
    }

    return answer
}

复杂度分析

时间复杂度：$O(n)$，只有一趟遍历，循环体内是两次异或，全是常数级位运算，没有排序也没有哈希查询带来的隐藏开销。

空间复杂度：$O(1)$，只用了 n、answer、i 三个标量，不随数组规模增长，也没有修改输入数组。

关键点总结

值域封闭且已知，就说明「应该有什么」可以凭空构造出来，问题立刻从查找转成「构造出的全集」与「实际集合」求差，这是一大类缺失/重复类题目的共同入口。

「找出唯一出现奇数次的元素」就该想到异或：x ^ x = 0 让成对的元素自动消失，$O(1)$ 空间取代了哈希表的 $O(n)$ 空间，本质是把「精确计数」降级成「奇偶计数」。

异或满足交换律和结合律，所以对乱序输入天然免疫，不需要排序作为前置步骤——面试时主动点出这一条，能说明你理解的是运算性质而不是背下来的模板。

累加器的初值可以用来消化「长度对不齐」：全集比数组多一项，就把那一项塞进初值，从而把两趟循环合成一趟，这个技巧在配对类问题里反复出现。

面试视角：面试官问这题几乎一定会追问「不用额外空间怎么做」和「求和法有什么风险」。标准答法是：异或法 $O(n)$ 时间 $O(1)$ 空间且永不溢出；求和法思路同样成立但 $n(n+1)/2$ 在 int 下会溢出，必须用 long。能主动比较这两条路并指出溢出差异，比只写出代码得分高得多。

不要为边界写特判，而要检验主逻辑是否天然覆盖边界：空数组、缺 0、缺 n 全都不需要额外分支，这是判断实现是否干净的快速自检。

易错点总结

错误写法：int answer = 0; 后只写 answer ^= i ^ nums[i] → 全集里的 n 从未进账。nums = [0]（n = 1，缺 1）会返回 0 ^ 0 ^ 0 = 0，答案凭空少了一位。

错误写法：写成 answer ^= nums[i] ^ nums[i]，把下标误写成元素 → 每一项自己和自己抵消，nums = [3, 0, 1] 恒返回初值 3，与输入完全无关。

错误写法：用求和法但写 int sum = n * (n + 1) / 2; → n = 10^5 时 n * (n + 1) 约 $10^{10}$，int 相乘先溢出成负数，nums = [0..99999] 缺尾项这类用例会返回一个荒谬的负值。要么全程用 long，要么改用异或。

错误写法：for (int i = 0; i <= n; ++i) answer ^= i ^ nums[i]; → i = n 时 nums[n] 越界，Java 抛 ArrayIndexOutOfBoundsException，Go 直接 panic。全集的第 n 项应该由初值承担，不能靠扩大循环范围来补。

错误写法：先 Arrays.sort(nums) 再逐位比对 i != nums[i] → 结果虽然对，但时间退化成 $O(n\log n)$ 且原地改写了调用方传入的数组；面试中被追问「能不能不排序」时无话可说。

错误写法：开 boolean[] seen = new boolean[n + 1] 打标记再回扫 → nums 长度 $10^5$ 时额外占用 $10^5$ 的空间，直接违反常数空间的要求；这是朴素解，不该作为最终答案交出去。

错误写法：为空数组加 if (nums.length == 0) return 0; 之外，还给「缺 0」补一句 if (nums[0] != 0) return 0; → 数组是乱序的，nums = [3, 0, 1] 的首元素本来就不是 0，这句特判会错误地返回 0 而不是 2。

错误写法：把返回值写成 nums[answer] 或 answer + 1 → 累加器里存的已经是缺失值本身，不是下标也不是「前一个数」。nums = [3, 0, 1] 会分别返回 1 和 3，都不是 2。

错误写法：用 answer += i - nums[i] 代替异或 → 差值法本身可行，但每一项都是有符号加减，中间量可能为负；一旦有人把 answer 声明成无符号类型或在 Go 里改用 uint，中途下溢会得到巨大的正数。异或没有这个隐患。

错误写法：Go 里写 for i := range nums { answer ^= i ^ nums[i+1] } → 越界 panic；range 给出的下标已经能直接配对当前元素，不需要任何偏移。

相似题目

题目	难度	考察点
268. 丢失的数字	简单	与本题完全同题，可直接套用一趟异或的写法
136. 只出现一次的数字	简单	不需要构造全集，成对元素已在数组内，直接把整个数组异或起来即可
面试题 17.19. 消失的两个数字	困难	缺两个数，总异或值需按最低置 1 位分成两组，才能把两个答案拆开
645. 错误的集合	简单	同时存在一重复一缺失，异或结果是两者的混合，需要分组或改用原地标记
448. 找到所有数组中消失的数字	简单	缺失个数不定，标量装不下，改用「把下标处的值取负」做原地标记
41. 缺失的第一个正数	困难	值域不再封闭，需靠原地置换把 `x` 换到下标 `x-1`，再扫首个错位
287. 寻找重复数	中等	求的是重复而非缺失，异或会被偶数次出现抵消，需转成环形链表找入口或二分值域