448. 找到所有数组中消失的数字
难度：简单 | 主题：数组、哈希表
题目
给你一个含 n 个整数的数组 nums，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。要求不使用额外空间且时间复杂度为 O(n)。
示例
nums = [4,3,2,7,8,2,3,1] → 输出 [5,6]
解释：长度为 8，缺失 5 和 6
思路
先讲个故事：教室点名
你是老师，班上 n 个学生学号是 1 到 n。你点名时发现有些人没来，但你不准拿额外的纸笔记——只能用手里的花名册本身做标记。
你想了个办法：每个被点到的学生，就在自己的座位上放本书占位。点完一圈，空座位就是缺席的人。
对应到数组：值就是学号，下标减 1 就是座位号。每个值出现时，把对应座位号位置的值取负作为标记。最后遍历一遍，值还为正的位置就是没人坐过的座位——下标 +1 就是消失的数字。
引导式推导：从暴力到原地
暴力法：用哈希集存所有出现的数，再遍历 1 到 n 检查缺失。O(n) 时间 O(n) 空间——题目要求不用额外空间。
优化方向：没有额外空间 → 拿数组本身当哈希表。
关键洞察：数组的值域 [1, n] 和下标域 [0, n-1] 天然一一对应。
| 值 | 1 | 2 | 3 | … | n |
|---|---|---|---|---|---|
| 下标 | 0 | 1 | 2 | … | n-1 |
所以值 x 出现，就是在告诉下标 x-1 的位置：「我被访问过了」。
怎么标记？取负。遍历每个数 num，把 nums[abs(num) - 1] 取负。最后遍历，值为正的位置就是没有被访问过的——即缺失的数字。
graph LR A["遍历 nums"] --> B["取 idx = abs(num)-1"] B --> C["nums[idx] 取负"] C --> D["遍历完成"] D --> E["值为正的位置 → 缺失"]
代码
def findDisappearedNumbers(self, nums):
for num in nums:
idx = abs(num) - 1 # 值映射到下标（减1是因为值从1开始）
nums[idx] = -abs(nums[idx]) # 标记为负数，表示该下标+1出现了
return [i + 1 for i, num in enumerate(nums) if num > 0] # 正数位置就是缺失的
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(n) | 两遍线性遍历 |
| 空间 | O(1) | 不计输出，原地修改 |
实战考量
频率分析
出现在：字节/腾讯/阿里约 20% 的同类题会考这种「原地哈希」技巧。核心是看你能不能想到把数组本身当哈希表用。
延伸思考
Q：为什么不用集合？
A：集合需要 O(n) 额外空间，题目明确要求 O(1)。但可以先用集合讲思路，再优化到原地。
Q：用取负标记，如果数组中有 0 怎么办？
A：题目保证值域 [1, n]，没有 0。如果有 0，可以用 +n 标记（值加 n，最后检查 ≤ n 的），取模还原索引。
Q：如果既要找消失的数字，又要找重复的数字呢？
A：数学法——求和与平方和，解方程组。或者原地标记时，被标记两次的位置可以推断重复。
Q：标记法会不会把后续要读的值搞乱？
A：不会。用 abs(num) 取原始值，负号只用来标记，不影响索引计算。
易错点
-
必须用
abs(num)读值，因为前面的标记可能已经把它变负数了 -
最后收集的是
i + 1不是i -
循环内不要调
count()——会变成 O(n²)
生活类比
花名册点名 → 原地哈希
想象你手里只有一张名单表，不能拿额外的纸。
每点到一个人，就在他名字后面画个✓。
点名结束，没打✓的就是缺席的人。
画✓是取负，没打✓的是正数——下标就是座位号，数组就是花名册。
相关题目
| 题目 | 关系 |
|---|---|
| 268丢失的数字 | 同族，找缺失的一个数，更简单 |
| 41缺失的第一个正数 | 原地哈希进阶版，条件更复杂 |
| 287寻找重复数 | 原地标记思想，但用快慢指针 |
→ 返回题单：LeetCode学习路线图 > 一、数组与哈希（含双指针、矩阵）
速记卡（面试闪卡）
Q1：一句话讲清「448. 找到所有数组中消失的数字」到底是什么？
A：在长度 n、值域 1~n 的数组里找出所有消失的数字，原地标记、不占额外空间。
Q2：题目理解 —— 要你交出哪些缺席者？ —— 怎么理解？
A：像老师点名，学号 1 到 n，不准拿额外纸笔，只能在本上画钩。你要把没来的人挑出来。英文：Find Disappeared Numbers。
Q3：核心思路 —— 怎么把数组当哈希表？ —— 怎么理解？
A：像在花名册上给到场者打钩：值 x 出现就把座位 x-1 取负占位，最后正数座位就是缺席者。英文：In-place Hashing。
Q4：代码实现 —— 两遍扫描怎么写？ —— 怎么理解？
A：像巡检员绕场两圈：第一圈每人数 idx=abs(num)-1，把该位取负做标记；第二圈收集仍为正的下标+1。英文：Two-pass Scan。
Q5：复杂度与实战 —— 易错点在哪？ —— 怎么理解？
A：像对账：时间 O(n) 两遍线性，空间 O(1) 原地改。易错在必须用 abs 读值、收集 i+1 而非 i。英文：In-place Marking。
Q6：核心速记主线有哪些？
-
题意：值域 [1,n] 对应下标 [0,n-1]，找缺失的数字
-
原地哈希：值 x 出现就把 nums[x-1] 取负做标记
-
收集时只取仍为正的下标，结果要 i+1
-
必须用 abs(num) 读值，负号只是标记不影响索引
-
时间 O(n)、空间 O(1)，不用额外集合
口诀
A：消失数字藏阵中，
取负占位标记工；
两遍扫描常数费，
原位对账现影踪。