题目描述
思路解析
一句话答案：LeetCode 448 找到所有数组中消失的数字的原地解法是符号标记：值域恰好是 1 到 n、与下标一一对应，第一遍读到数 x 就把下标 |x|-1 处的值翻成负数当「打卡」，第二遍收集仍为正数的位置，其下标加一就是从没出现过的数，时间 O(n)、额外空间 O(1)（返回数组不计）。
这道题真正在问什么
数组长度为 n，每个元素都落在 1 到 n 之间、可能重复，要求找出 1 到 n 中没出现在数组里的所有数。比如 [4,3,2,7,8,2,3,1] 里，5 和 6 从没露过面。题目附加的挑战是 O(n) 时间加 O(1) 额外空间——这条限制把最顺手的哈希集合排除在外，正是整道题的题眼。
哈希集合为什么不达标，突破口在哪
把出现过的数装进哈希集合，再从 1 到 n 逐个查缺，时间 O(n) 没问题，但集合要 O(n) 空间。想省掉这份空间，就得注意题目埋下的巧合：值域是 1 到 n，数组下标是 0 到 n-1，两者一一对应——值 v 天然对应下标 v-1。也就是说，数组自身就能充当那张「出勤表」，每个格子负责登记一个值来没来过，不需要另开任何结构。
负号凭什么能当标记用
出勤表需要在每个格子里记一个「来过或没来过」的标志位，可格子里已经存着原数据了。妙处在于：题目保证所有值都是正数，符号位是闲置的信息通道。把某格翻成负数，表示「它负责的那个值出现过」；而随时取绝对值就能还原原值——标记和数据挤在同一个格子里互不干扰，这正是 O(1) 空间的来源。
两遍扫描各自为什么成立
第一遍打卡：读到一个数先取绝对值（它可能已被前面的操作翻成负数），定位到下标 |x|-1，只在那一格还是正数时才翻负。「只翻一次」很关键——重复值会两次定位到同一个格子，无脑取反会把负号翻回正数，擦掉已有的打卡记录。
第二遍收集：扫完之后某格仍是正数，说明从头到尾没有任何数来给它打过卡，它负责的值（下标加一）就从未出现过，收进答案。每个格子的符号忠实记录了对应值出现与否，所以答案不重不漏。
复杂度与这套技巧的适用边界
时间 O(n)：标记一遍加收集一遍，两趟线性扫描。额外空间 O(1)：借的是输入数组自己的符号位，返回数组按惯例不计。要注意这套原地标记的前提是「值域与下标同构」：值域里出现 0、负数或远超 n 的数就借不了位，只能退回哈希集合的 O(n) 空间方案；另外它改写了输入数组，如果调用方要求输入只读，同样得换普通做法。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条对应关系：「值 v ↔ 下标 v-1，把对应下标标负 = 给这个值打卡」。下面两遍扫描全在套它。
负号是「打卡标记」，绝对值才是真正的数——这样标记和原值互不干扰，空间 O(1)。
初始数组，所有值都是正数（还没人打卡）。开始第一遍扫描：每读到一个数 x，就去给「值 x」打卡——把下标 |x|-1 处的值翻成负数。
第 1 步：当前读到的值是 4（对应下标 3）。下标 3 那格还是正的，翻成负数 -7，表示「值 4 出现过」。
第 2 步：当前读到的值是 3（对应下标 2）。下标 2 那格还是正的，翻成负数 -2，表示「值 3 出现过」。
第 3 步：当前读到的值是 2（对应下标 1）。下标 1 那格还是正的，翻成负数 -3，表示「值 2 出现过」。
第 4 步：当前读到的值是 7（对应下标 6）。下标 6 那格还是正的，翻成负数 -3，表示「值 7 出现过」。
第 5 步：当前读到的值是 8（对应下标 7）。下标 7 那格还是正的，翻成负数 -1，表示「值 8 出现过」。
第 6 步：当前读到的值是 2（对应下标 1）。下标 1 那格已经是负数了，说明值 2 之前已被打过卡（重复值），不再重复翻负，保持负号即可。
第 7 步：当前读到的值是 3（对应下标 2）。下标 2 那格已经是负数了，说明值 3 之前已被打过卡（重复值），不再重复翻负，保持负号即可。
第 8 步：当前读到的值是 1（对应下标 0）。下标 0 那格还是正的，翻成负数 -4，表示「值 1 出现过」。
第 9 步：当前读到的值是 9（对应下标 8）。下标 8 那格还是正的，翻成负数 -9，表示「值 9 出现过」。
第 10 步：当前读到的值是 9（对应下标 8）。下标 8 那格已经是负数了，说明值 9 之前已被打过卡（重复值），不再重复翻负，保持负号即可。
第 11 步：当前读到的值是 11（对应下标 10）。下标 10 那格还是正的，翻成负数 -11，表示「值 11 出现过」。
第 12 步：当前读到的值是 5（对应下标 4）。下标 4 那格还是正的，翻成负数 -8，表示「值 5 出现过」。
第一遍扫描结束。现在数组里：被打过卡（出现过）的位置是负数，从没被打卡的位置仍是正数。接下来第二遍，找出所有「还是正数」的下标——它们对应的值 i+1 就是消失的数。
看下标 0：值是 -4，是负数，说明「值 1」出现过（被打过卡），不是消失的数，跳过。
看下标 1：值是 -3，是负数，说明「值 2」出现过（被打过卡），不是消失的数，跳过。
看下标 2：值是 -2，是负数，说明「值 3」出现过（被打过卡），不是消失的数，跳过。
看下标 3：值是 -7，是负数，说明「值 4」出现过（被打过卡），不是消失的数，跳过。
看下标 4：值是 -8，是负数，说明「值 5」出现过（被打过卡），不是消失的数，跳过。
看下标 5：值是 2，是正数，说明从没有数给「值 6」打过卡 ⇒ 6 消失了，加入答案。
看下标 6：值是 -3，是负数，说明「值 7」出现过（被打过卡），不是消失的数，跳过。
看下标 7：值是 -1，是负数，说明「值 8」出现过（被打过卡），不是消失的数，跳过。
看下标 8：值是 -9，是负数，说明「值 9」出现过（被打过卡），不是消失的数，跳过。
看下标 9：值是 9，是正数，说明从没有数给「值 10」打过卡 ⇒ 10 消失了，加入答案。
看下标 10：值是 -11，是负数，说明「值 11」出现过（被打过卡），不是消失的数，跳过。
看下标 11：值是 5，是正数，说明从没有数给「值 12」打过卡 ⇒ 12 消失了，加入答案。
第二遍扫描完毕。仍是正数的下标是 5、9、11，它们对应的值 6、10、12 从没出现过——这就是所有消失的数：[6, 10, 12]。
边界：全到齐返回空、全是同一个数则其余都消失、单元素。原地标记都能自然覆盖。
两个高频追问：原地法依赖「值域 1..n 与下标同构」；若数组只读就退回哈希集合 O(n) 空间。
参考代码
def findDisappearedNumbers(nums): n = len(nums) for x in nums: # 第一遍：标记 idx = abs(x) - 1 # 值 x 对应下标 if nums[idx] > 0: # 只在还是正数时翻负 nums[idx] = -nums[idx] res = [] for i in range(n): # 第二遍：收集 if nums[i] > 0: # 仍为正 → 值 i+1 没出现 res.append(i + 1) return res复杂度
- 时间：O(n)，两遍线性扫描：标记一遍 + 收集一遍
- 空间：O(1)，借数组自身的正负号记录，不额外开哈希表（返回数组不计）
易错点
面试追问把动画讲成自己的话
追问为什么这道题能不用额外哈希表？换个值域还行吗？
追问如果不能修改原数组（要保持只读）怎么办？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
搜索二维矩阵 II
LeetCode 240 · 中等 · 沿着 数组 & 哈希 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题