LeetCode 448. 找到所有数组中消失的数字
题目核心
给你一个含 n 个整数的数组 nums，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下完成吗？返回的数组不计入空间复杂度。
例如：
输入：nums = [4, 3, 2, 7, 8, 2, 3, 1]
输出：[5, 6]
解释：长度 n=8，范围 [1..8]，其中 5 和 6 没有出现。解题思考过程
第一步：朴素做法 — 哈希集合
把 nums 里的数全丢进 set，然后从 1 到 n 扫一遍，不在 set 里的就是答案。
时间：O(n)
空间：O(n)（set 的大小）能过，但用到了额外空间，不符合进阶要求。
第二步：能不能把"有没有出现"的信息存到数组本身里？
题目给了关键条件：每个数都在 [1, n] 之间，而且我们关心的答案也在 [1, n]。数组本身刚好有 n 个位置，天然就像一个"索引 = 数 - 1"的表。
如果能给那些已经出现过的数做上"我来过"的标记，那么最后没有标记的位置对应的数就是消失的数字。
第三步：怎么在不破坏原数据的前提下做标记？
思路：遍历每个数 nums[i]，找到它应归属的位置 idx = nums[i] - 1（因为数从 1 开始），给 nums[idx] 加一个固定的"大于 n 的偏移"（比如加 n）。
由于任何没出现过的位置它的值最多只是被"原始值 ± 若干次加 n"影响，只要我们取模还原原始值，就能拿到真正的数，不会破坏原数据。
为什么加 n ？因为 n 是最大值，任何"出现过一次"的位置加 n 之后会严格大于 n；而没出现过的位置，最多只能在别的数通过它时被加 n，或者保持原值 ≤ n —— 但注意，即使在扫描时 idx 计算用到了它，取模之后还是能拿到真实值。
最后：如果某位置 i 的最终值 ≤ n，说明从来没有任何数等于 i+1 出现过把它加 n → 所以 i+1 就是消失的数字。
这就是贴的代码思路。
当前解法：原地加 n 标记
/**
* @param {number[]} nums
* @return {number[]}
*/
var findDisappearedNumbers = function (nums) {
let n = nums.length;
// 把所有在范围的数字 +n
for (let i = 0; i < n; i++) {
const x = (nums[i] - 1) % n;
nums[x] += n;
}
const ans = [];
for (let i = 0; i < n; i++) {
if (nums[i] <= n) {
ans.push(i + 1);
}
}
return ans;
};代码逐行解释
1. 第一轮：标记出现过的数
for (let i = 0; i < n; i++) {
const x = (nums[i] - 1) % n;
nums[x] += n;
}对每个元素 nums[i]：
nums[i]可能已经因为之前别人加了 n而变大了，但我们关心的是它原本表示什么数字，所以用% n还原它的原始"数值身份"。- 例如：原来
nums[i]=3，被之前标记过变成了n+3，再%n又能得到 3。
- 例如：原来
- 于是
x = (原值 - 1) % n就是它应该去标记的索引（位置 x 对应数字 x+1）。 - 给
nums[x] += n，相当于在 x 位置上"盖了章"——这个数字（x+1）出现过。
2. 第二轮：找没被盖过章的位置
const ans = [];
for (let i = 0; i < n; i++) {
if (nums[i] <= n) {
ans.push(i + 1);
}
}
return ans;扫描结束后：
- 如果某个位置
i的值最终还 ≤ n，说明从来没有任何数等于 i+1 来给它盖章 →i+1没出现过，就是消失的数。 - 如果它已经
> n，说明出现过（可能多次，但 ≥ 1 次）。
执行过程示例
nums = [4, 3, 2, 7, 8, 2, 3, 1]，n = 8：
初始：[4, 3, 2, 7, 8, 2, 3, 1]
逐个 i 扫描：
i=0: nums[0]=4, x=(4-1)%8=3 → nums[3] += 8 → [4,3,2,15,8,2,3,1]
i=1: nums[1]=3, x=(3-1)%8=2 → nums[2] += 8 → [4,3,10,15,8,2,3,1]
i=2: nums[2]=10, x=(10-1)%8=9%8=1 → nums[1] += 8 → [4,11,10,15,8,2,3,1]
i=3: nums[3]=15, x=(15-1)%8=14%8=6 → nums[6] += 8 → [4,11,10,15,8,2,11,1]
i=4: nums[4]=8, x=(8-1)%8=7 → nums[7] += 8 → [4,11,10,15,8,2,11,9]
i=5: nums[5]=2, x=(2-1)%8=1 → nums[1] += 8 → [4,19,10,15,8,2,11,9]
i=6: nums[6]=11, x=(11-1)%8=10%8=2 → nums[2] += 8 → [4,19,18,15,8,2,11,9]
i=7: nums[7]=9, x=(9-1)%8=8%8=0 → nums[0] += 8 → [12,19,18,15,8,2,11,9]最终数组：[12, 19, 18, 15, 8, 2, 11, 9]
第二次扫描找 nums[i] <= 8：
i=0: 12 > 8 → 不
i=1: 19 > 8 → 不
i=2: 18 > 8 → 不
i=3: 15 > 8 → 不
i=4: 8 <= 8 → ✅ ans 推 5
i=5: 2 <= 8 → ✅ ans 推 6
i=6: 11 > 8 → 不
i=7: 9 > 8 → 不
ans = [5, 6] ✓为什么取模还原是对的？
假设某个数 v 出现过，它对应的位置在标记时被加 n，之后再访问这个位置时：(new_v - 1) % n = (v + k*n - 1) % n = (v - 1) % n —— 结果和不加 n 一样。所以即使被反复加 n，%n 永远能还原它的原始身份。
替代解法一：哈希集合
面试中如果没想到原地算法，可以先写这个保底：
var findDisappearedNumbers = function (nums) {
const set = new Set(nums);
const ans = [];
for (let i = 1; i <= nums.length; i++) {
if (!set.has(i)) ans.push(i);
}
return ans;
};- 时间 O(n)
- 空间 O(n)（set）
替代解法二：正负号原地标记
思路类似，但不是加 n，而是给"对应位置的值"翻转为负数。如果最终某位置还是正，说明没出现。
var findDisappearedNumbers = function (nums) {
const n = nums.length;
for (let i = 0; i < n; i++) {
const idx = Math.abs(nums[i]) - 1;
if (nums[idx] > 0) nums[idx] = -nums[idx];
}
const ans = [];
for (let i = 0; i < n; i++) {
if (nums[i] > 0) ans.push(i + 1);
}
return ans;
};和加 n 的版本等价，个人更喜欢这个——因为代码里绝对值的语义更直观，不需要考虑 %n 还原。
易错点
- 计算 x 一定要取模：
(nums[i] - 1) % n。不写%n的话，当nums[i]已经被之前的操作加了 n 之后，索引会越界。 - 第二轮判断条件是
<= n不是< n：未出现过的位置可能值正好是 n 本身，比如示例中nums[4]=8，如果写成<n就会漏。 - 消失的数是
i+1不是i：因为题目里数从 1 开始，索引从 0 开始。 - 正负号标记要绝对值：在替代解法里取索引时，
nums[i]可能已经被之前的人翻成负数了，所以要用Math.abs(nums[i]) - 1。 - 同一个数重复出现时也能处理：比如示例里的
2和3出现了两次，重复给对应索引加 n / 翻负不影响——只要"至少被标记过一次"就够了，次数多少不影响最终判断。
复杂度
- 时间复杂度：
O(n)。两轮线性扫描，内部都是 O(1) 操作。 - 空间复杂度：
O(1)（除了返回的 ans，没有开额外数组/哈希）。
满足题目"不使用额外空间 + O(n) 时间"的进阶要求。