LeetCode 448. 找到所有数组中消失的数字
目录
题目描述
题意分析
给一个长度为
n的数组nums，其中每个元素都落在 $[1, n]$ 这个闭区间内。把1到n这n个数当成一份完整名单，数组里出现过的算「到场」，要求把所有没在数组里出现过的数字全部找出来并返回。
题面里有两个数量关系必须先咬死：值域是 $[1, n]$，数组长度也是
n。值的个数和坑位的个数完全一样，这是整道题的题眼。它意味着「有数字重复出现」和「有数字一个都没出现」是同一件事的两面——重复了几个，就必然缺了几个。反过来说，如果不允许重复，答案必然是空。
值域与下标一一对应还带来第二层信息：数字
v可以唯一地映射到下标v - 1，这个映射是双射。也就是说，我们完全不需要一张额外的哈希表来记录「谁出现过」，因为数组自己的下标空间就是一张现成的、大小刚好合适的表。题目进阶要求 $O(n)$ 时间且不使用额外空间，正是在逼你利用这层对应关系。
但下标空间被「占用」了：
nums里已经存着输入数据，不能直接拿某一格当布尔标记，否则原数据丢了后面还没遍历到的元素就读不出来。于是问题变成：如何在同一个int里同时保存「原值」和「一个布尔位」。约束里的nums[i] >= 1恰好留下了符号位这块空地——所有值天然为正，负号从未被使用过，可以拿它当标记位。
边界方面：
n最小是 1，此时数组只能是[1]，没有缺失，返回空列表；数组可能全是同一个值（如[2, 2]），此时同一个下标会被重复标记，代码必须能容忍「标记已经打过」这种情况而不把它再翻回正数；结果为空时要返回空列表而不是null。
解法：利用下标原地标记出现过的数字
核心思路
最直接的写法是开一个长度
n + 1的boolean数组（或者一个HashSet），扫一遍nums把出现过的数字打上标记，再从 1 到 n 检查哪些没被标记。这个做法完全正确，时间也是 $O(n)$，瓶颈只有一个：它额外用了 $O(n)$ 的空间，而进阶要求把这块空间省掉。
关键观察是那张
boolean表和输入数组长度一模一样、下标一一对应。既然形状相同，就没必要真的开一块新内存，只要能在nums的每一格上额外挂一个布尔位就行。而 $1 \le nums[i] \le n$ 保证了所有元素恒为正，符号位是完全空闲的：把nums[idx]取反，就等价于在这块假想的boolean表的第idx位写下 true，而元素的绝对值仍然完好地保留着原始数据。
于是第一趟遍历的循环不变量是：处理完前
i个位置后，对任意下标j，nums[j] < 0当且仅当数字j + 1在nums的前i个元素中出现过；并且对任意j，|nums[j]|恒等于该位置的原始输入值。第一条说明标记是准确的，第二条说明数据没被破坏——正是第二条要求我们每次读取元素时都必须先取绝对值。
第一趟结束后，不变量对整个数组成立：
nums[j] < 0表示数字j + 1出现过，nums[j] > 0表示它一次都没出现。第二趟只需把所有仍为正数的下标j转成j + 1收集起来，就是答案。
重复出现的元素会让同一个下标被标记两次。这就是代码里要判
nums[idx] > 0才取反的原因——如果无脑写nums[idx] = -nums[idx]，第二次标记会把负数翻回正数，等于把「出现过」的记录擦掉了。
解题步骤
- 第一趟遍历，对每个元素先取绝对值：
int value = Math.abs(num)。因为遍历到位置i时，nums[i]可能早已被前面的某次标记改成了负数，直接拿它算下标会得到负值并越界。取绝对值恢复的正是不变量第二条所保证的原始值。- 算出映射下标
idx = value - 1：值域是 $[1, n]$、下标是 $[0, n-1]$，减一是唯一正确的对齐方式。这里不需要任何范围校验，因为题目已经保证了值域。- 只在
nums[idx] > 0时执行nums[idx] = -nums[idx]：这个判断是幂等性保护。数字重复出现时第二次会命中已经是负数的格子，跳过即可；漏掉这个判断会把标记翻回正号，导致一个真正出现过的数字被误报成缺失。- 第二趟遍历收集答案：对每个下标
i，若nums[i] > 0就把i + 1加入结果。加一是第二步减一的逆运算；直接加i会让整个答案偏小 1。- 返回结果列表：没有缺失时自然返回空列表，不需要特判。
以
nums = [4, 3, 2, 7, 8, 2, 3, 1]走一遍（n = 8，期望[5, 6]）。第一趟按下标推进，每轮列出「读到的原值 → 标记的下标 → 数组状态」。
i = 0：读到 4，取绝对值仍是 4，idx = 3，nums[3] = 7 > 0，取反。数组变为[4, 3, 2, -7, 8, 2, 3, 1]。
i = 1：读到 3，idx = 2，nums[2] = 2 > 0，取反。数组变为[4, 3, -2, -7, 8, 2, 3, 1]。
i = 2：读到-2，这里就是取绝对值的用武之地——它的原值是 2，idx = 1，nums[1] = 3 > 0，取反。数组变为[4, -3, -2, -7, 8, 2, 3, 1]。
i = 3：读到-7，原值 7，idx = 6，nums[6] = 3 > 0，取反。数组变为[4, -3, -2, -7, 8, 2, -3, 1]。
i = 4：读到 8，idx = 7，nums[7] = 1 > 0，取反。数组变为[4, -3, -2, -7, 8, 2, -3, -1]。
i = 5：读到 2，idx = 1，nums[1] = -3已经是负数，跳过。这正是 2 第二次出现的情形，若强行取反会把nums[1]变回 3，最终把数字 2 误判为缺失。
i = 6：读到-3，原值 3，idx = 2，nums[2] = -2已为负，跳过。
i = 7：读到-1，原值 1，idx = 0，nums[0] = 4 > 0，取反。数组变为[-4, -3, -2, -7, 8, 2, -3, -1]。
第二趟扫描：下标 0 到 3 全是负数，跳过；
i = 4处nums[4] = 8 > 0，收集5；i = 5处nums[5] = 2 > 0，收集6；下标 6、7 为负，跳过。返回[5, 6]，与期望一致。注意最终留在正号位置上的 8 和 2 是原始输入值本身，它们的数值和答案毫无关系，判断依据只有符号，不是数值。
代码实现
class Solution {
// 可以把原数组当成访问标记表：看到值 value 时，将 nums[value - 1] 置为负数。
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int num : nums) {
int idx = Math.abs(num) - 1;
if (nums[idx] > 0) {
nums[idx] = -nums[idx];
}
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
res.add(i + 1);
}
}
return res;
}
}
func findDisappearedNumbers(nums []int) []int {
// 可以把原数组当成访问标记表：看到值 value 时，将 nums[value - 1] 置为负数。
for i := 0; i < len(nums); i++ {
idx := nums[i]
if idx < 0 {
idx = -idx
}
idx--
if nums[idx] > 0 {
nums[idx] = -nums[idx]
}
}
res := make([]int, 0)
for i, val := range nums {
if val > 0 {
res = append(res, i+1)
}
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：两趟独立的线性遍历，没有嵌套循环也没有回退，每轮只做一次取绝对值、一次比较和至多一次赋值，全是常数操作，合计 $2n$ 次基本操作。
- 空间复杂度：$O(1)$（不计返回值）。凭什么：标记信息全部寄生在输入数组的符号位上，没有开辟任何哈希表或布尔数组，只用了
idx、i这几个标量。结果列表长度取决于缺失数字个数，它是题目要求返回的输出本身，按惯例不计入额外空间。
关键点总结
- 当值域和下标空间大小相同且能一一对应时，输入数组本身就是一张现成的哈希表，「值
v↔ 下标v - 1」是这类题的统一入口，看到「长度为 n、元素在 1 到 n」就该立刻往这个方向想。- 想在不额外开空间的前提下附加信息，就要找数据里没被使用的表示位：本题元素恒为正，符号位空闲；若元素可能为负，则可以改用「加
n + 1后取模」或交换归位的方式携带标记。- 原地修改数组时必须区分「数据的当前存储形态」和「数据的原始语义」，取绝对值就是从前者还原到后者的翻译层，任何一次读取都要过这道翻译。
- 标记操作必须是幂等的，
if (nums[idx] > 0)的守卫比无条件取反更本质——只要输入允许重复，取反类标记就一定要加这层保护。- 「重复的个数等于缺失的个数」这个抽屉原理式的观察，是本题与 442、645、287 共享的底层结构，答对本题后往往会被追问其中之一。
- 面试时值得主动说的是「为什么可以借符号位」以及「如果元素允许为 0 或负数该怎么改」，这两句能证明你理解的是原地标记这个手法，而不是背了一段模板。
易错点总结
- 读元素时忘记取绝对值：
[4, 3, 2, 7, 8, 2, 3, 1]走到i = 2时读到的是已被标记成-2的值，idx = -3直接抛数组越界异常。- 无条件执行
nums[idx] = -nums[idx]，不判断是否已为负：[2, 2]中数字 2 被标记两次，nums[1]先变负再翻回正，最终结果算出缺失为[2]，而正确答案是[1]。- 映射下标写成
idx = value：[1, 1]中读到 1 会去标记nums[1]，n = 2时值 2 又会去访问nums[2]造成越界；即便不越界，整张标记表也整体错位一格。- 收集答案时加入
i而不是i + 1：[4, 3, 2, 7, 8, 2, 3, 1]会返回[4, 5]，整体比正确答案[5, 6]小 1。- 第二趟判断写成
nums[i] < 0收集：条件取反，[1, 1]会返回出现过的数字[1]，而不是缺失的[2]。- 在同一趟循环里边标记边收集：
[2, 1]里遍历到i = 0时数字 1 还没被标记，nums[0]仍为正会被误收成缺失，结果多出一个不存在的答案。必须等第一趟全部标记完再统计。- 第一趟遍历时把
nums[i]缓存在循环外或用旧值判断：读的是快照而不是当前存储值，[3, 3, 1]这类含重复的用例里守卫失效，等价于漏掉幂等保护。- 返回前忘记把数组恢复成正数：单看本题判题不影响，但如果面试官追问「这个函数会不会有副作用」，答不上来就暴露了没意识到它破坏了入参；工程场景中调用方拿到的是一个满是负数的数组。
- 用排序后比对下标的做法：
[4, 3, 2, 7, 8, 2, 3, 1]结果虽对，但时间退化到 $O(n \log n)$，达不到进阶要求，面试中会被要求重写。- 用
HashSet装完再从 1 到 n 查询：正确但额外占用 $O(n)$ 空间，本题的考点恰恰是把这块空间省掉，只写这版基本等于没答到点上。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 442. 数组中重复的数据 | 中等 | 同一套符号标记，但收集的是「标记时发现已为负」的那些数，是本题的镜像面 |
| 645. 错误的集合 | 简单 | 要同时输出重复数和缺失数，等于把 442 与本题的两种收集逻辑合并进一趟遍历 |
| 268. 丢失的数字 | 简单 | 值域是 0 到 n 且只缺一个，可直接用求和差或全体异或，不必原地标记 |
| 41. 缺失的第一个正数 | 困难 | 元素可以为负或超出 n，符号位不再空闲，必须改用交换归位把 v 换到下标 v - 1
|
| 287. 寻找重复数 | 中等 | 明确禁止修改数组，符号标记不可用，要转成链表环入口用快慢指针求解 |
| 面试题 17.04. 消失的数字 | 简单 | 与 268 同题，值域含 0 且只缺一个，异或解法最短 |
| 剑指 Offer 03. 数组中重复的数字 | 简单 | 值域是 0 到 n-1，只要找出任意一个重复值即可，原地交换归位一次命中 |