LeetCode 448简单数组 · 原地标记
找到所有数组中消失的数字 图解题解
数字减一当下标、负号当标记，一趟扫描 O(n) 找出所有缺席号，额外空间 O(1)。
就像 8 个格子编号 0 到 7，但票面号是 1 到 8——念到票号 x，就去第 x-1 格打负号标记（不换掉格子里的数，只是让它变负）。扫完一轮，哪个格子还是正数，说明票号 格子+1 从没出现过，直接报缺席。
这道题到底在问什么
给你一个长度为 n 的数组 nums，每个元素都在区间 [1, n] 内（可能有重复）。请找出 1 到 n 中所有没在 nums 里出现过的数字，按数组返回。进阶：时间 O(n)、不开额外空间。
- 输入
- nums = [4,3,2,7,8,2,3,1]
- 输出
- [5,6]
- 输入
- nums = [1,1]
- 输出
- [2]
最优解：一步一步想明白
- 3好懂，但 seen 要占 O(n) 额外空间，过不了进阶要求。面试官追问「能不能不开 seen」，就得换思路。
- 4负号不改变数字大小，只是借符号位当一个「出现过」的标记。读数字时永远用 abs，就不怕它已经被打过勾。
- 5数字 4 对应下标 3，数字 8 对应下标 7记住这条映射：合法数字 1 到 8，正好对应下标 0 到 7。数字 1 找下标 0，数字 8 找下标 7，一一对应不浪费。
- 6i = abs(4) − 1 = 3，nums[3] 大于 0，取负读到 4，说明数字 4 出现过。跳到下标 3，nums[3]=7 是正的，取负变 −7。以后看见下标 3 是负数，就知道 4 已被标记。
- 7i = abs(3) − 1 = 2，取负读到 3，跳到下标 2，把 2 取负成 −2。注意标记的是「下标 2」这个格子，和它原来装的值 2 没关系。
- 8i = abs(2) − 1 = 1，取负读到 2，给下标 1 打勾。走到这里 2、3、4 都见过了。
- 9当前值已是负数，i = abs(−7) − 1 = 6这就是 abs 的用武之地。下标 3 此刻是 −7，但它原来代表的数字是 7。用 abs 拿回 7，跳到下标 6 打勾。如果偷懒不取 abs，下标就会算错。
- 10i = abs(8) − 1 = 7，取负读到 8，给最后一格下标 7 打勾，1 变 −1。
- 11if nums[1] 大于 0 → 不成立 → 不再取负第二个 2 又指向下标 1，但 nums[1] 已经是 −3。这里必须判一句「只有大于 0 才取负」，否则会把它翻回正数，等会儿误判成缺失。这是本题第一大坑。
- 12i = abs(−3) − 1 = 2，nums[2] 已是负数下标 6 现在是 −3，abs 还原成 3，本想给下标 2 打勾，但下标 2 早被标过了，跳过。abs + 判正负这套组合，让重复数字怎么读都不出错。
- 13i = abs(1) − 1 = 0，取负最后读到 1，给下标 0 打勾，4 变 −4。第一遍走完，所有出现过的数字都在数组里留下了「负号脚印」。
- 14扫一遍找正数：下标 4（值 8）、下标 5（值 2）第二遍扫描，只有下标 4 和 5 还是正数，说明 5 和 6 没被打过勾。下标 4 转成 5，下标 5 转成 6，答案就是 [5,6]。注意：要返回的是「下标+1」，不是格子里那个值。
- 15读 x=−7 → abs 还原 7 → 给下标 6 打勾把最容易绕晕的一步慢放：当前格 −7 是「被读的人」，下标 6 是「被打勾的人」，两者不是同一个。读靠 abs、打勾靠 abs(x)−1，永远分清这两个角色，这题就通了。
- 18长度 n、值在 1 到 n，这个信号一出现，就该想「值映射成下标 + 原地标记」。负号、置换、计数都是同一招的变体。
- 20两个 1 都指向下标 0拿 [1,1] 真跑一遍：第一个 1 把下标 0 标成 −1，第二个 1 如果不判「大于 0 才取负」，就会把 −1 又翻回 +1。第二遍一看下标 0 是正的，错把 1 当成缺失，输出错的 [1]。正确答案是 [2]。
- 24想系统练这一类「数组当哈希表」的题，去专题页跟着练，遇到卡点直接问 AI 助教小欧，或开通关训练把同类题一次刷透。
⚠️ 容易写错的地方
✗ 错：用 x−1 直接做下标
✓ 对：用 abs(x)−1
x 可能在之前被标成了负数，不取 abs 下标就算错。
✗ 错：见到 x 无脑取负
✓ 对：先判 nums[i] 大于 0 再取负
重复数字会让你把负号翻回正数，缺失数字就被漏判。
✗ 错：返回格子里的当前值
✓ 对：返回下标 i+1
缺失的数字是「下标+1」，不是该位置此刻装的数。
完整代码（Python / C++ / Java）
Python
class Solution:
def findDisappearedNumbers(self, nums):
for x in nums: # 第一遍：打勾
i = abs(x) - 1 # 读值要取 abs
if nums[i] > 0: # 只给没打过的取负
nums[i] = -nums[i]
ans = []
for i, x in enumerate(nums): # 第二遍：收答案
if x > 0:
ans.append(i + 1) # 返回下标+1
return ansC++
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
for (int x : nums) { // 第一遍：打勾
int i = abs(x) - 1; // 读值取 abs
if (nums[i] > 0) // 只给没打过的取负
nums[i] = -nums[i];
}
vector<int> ans;
for (int i = 0; i < (int)nums.size(); i++) // 第二遍
if (nums[i] > 0) ans.push_back(i + 1);
return ans;
}
};Java
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int x : nums) { // 第一遍：打勾
int i = Math.abs(x) - 1; // 读值取 abs
if (nums[i] > 0) // 只给没打过的取负
nums[i] = -nums[i];
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < nums.length; i++) // 第二遍
if (nums[i] > 0) ans.add(i + 1);
return ans;
}
}套路模板 · 值映射下标骨架（挖空）
# 适用：len(nums)=n 且 值都在 1..n，要找 缺失/重复
for x in nums:
i = abs(x) - 1 # ① 值→下标，读值务必取 abs
if nums[i] > 0: # ② 没标过才标（重复就跳过）
nums[i] = -nums[i] # 符号位 = 出现过
# ③ 收集条件按题意改：
# 448 缺失 → 第二遍取 nums[i] > 0 的 i+1
# 442 重复 → 第一遍发现 nums[i] < 0 时记下 i+1// len(nums)=n 且 值∈[1,n] 时套用
for (int x : nums) {
int i = abs(x) - 1; // ① 值→下标
if (nums[i] > 0) // ② 没标过才标
nums[i] = -nums[i]; // 符号位=出现过
}
// ③ 收集条件按题意改：448 收正下标+1 / 442 收已负的值// nums 长度 n 且 值∈[1,n] 时套用
for (int x : nums) {
int i = Math.abs(x) - 1; // ① 值→下标
if (nums[i] > 0) // ② 没标过才标
nums[i] = -nums[i]; // 符号位=出现过
}
// ③ 收集条件按题意改：448 收正下标+1 / 442 收已负的值复杂度
时间复杂度
O(n)
第一遍打勾、第二遍收答案，各扫一次，2n 步，去常数即 O(n)。
空间复杂度
O(1)
标记直接写回 nums，只用 i、x 两个变量；返回数组 ans 不计入额外空间。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 找到所有数组中消失的数字 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么能原地标记，不用额外空间？+
值都在 1 到 n，恰好能映射到下标 0 到 n−1。数组本身就够当哈希表，用符号位当「出现过」的标记位。
如果不让改原数组呢？+
退化成开 O(n) 的 seen 集合或布尔数组；或先排序再扫（O(n log n) 时间、O(1) 额外空间），用时间换空间。
和 442「找重复」是什么关系？+
同一套值映射下标：448 找「第二遍仍为正」的下标，442 找「想取负时已是负数」的那个值。框架一样，只换收集条件。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。