448. 找到所有数组中消失的数字（Find All Numbers Disappeared in an Array）

频次 ★★★ · 难度 🟢 · 高频：百度

题目

给定一个整数数组，其中 1 <= nums[i] <= n（n 为数组长度），有些元素出现两次，有些出现一次。找出所有在 [1, n] 范围内没有出现在数组中的数字。

示例：

输入: nums = [4, 3, 2, 7, 8, 2, 3, 1]
输出: [5, 6]

思路

原地标记法：

• 对于每个数 nums[i]，将其对应索引位置 nums[i]-1 处的值标记为负数
• 第二次遍历时，正值所在的位置就是缺失的数字

因为所有值都在 [1, n] 范围内，所以可以安全地用负号来标记”已出现”。

代码

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        int index = Math.abs(nums[i]) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            result.add(i + 1);
        }
    }
    return result;
}

复杂度

• 时间：O(n) — 两趟遍历
• 空间：O(1) — 不计输出数组

边界条件

• 数组恰好是 1..n 的排列（无缺失）：所有位置最终都是正数，第二次遍历结果为空列表。
• 所有数字都相同（如 [1,1,1]，n=3）：只有下标 0 会被标记（多次标记也没关系，if (nums[index] > 0) 保证同一位置不会被重复取负两次），下标 1、2 保持正数，正确返回 [2,3]。
• 数组长度为 1（[1]）：唯一位置被标记为负，结果为空列表，正确。

变式

• 找出重复的数字而不是缺失的数字（LeetCode 442 题）：同样用负号标记，当发现某个 nums[index] 已经是负数时，说明这个值之前出现过，即为重复值。
• 数字范围不是 [1,n] 而是任意范围：负号标记法失效（因为下标不能直接对应任意值），需要退回到 HashSet 或先做值域映射。

易错点

• 标记前要用 Math.abs(nums[i])，因为前面的标记操作可能已经把某个位置变成了负数，直接用 nums[i] - 1 做下标会得到错误的负索引。
• 标记时要判断 nums[index] > 0 才取负，否则同一个值出现 3 次以上时会被反复取负导致重新变回正数，破坏标记状态。

面试追问

• 这种”用数组自身存储的值当下标”的技巧还能用在哪些题目上？ 这是一类经典技巧，只要满足”数值范围恰好是 [1,n] 或 [0,n-1]”就可以把值和下标关联起来原地做标记，比如 41. 缺失的第一个正数（用交换代替取负）、寻找重复数字等。
• 为什么用取负号而不是用一个额外的布尔数组？ 额外布尔数组需要 O(n) 空间，而原数组本身有 n 个位置可以复用；取负号不改变数字的绝对值信息（后续还能用 Math.abs 还原），是一种”原地复用存储空间”的常见手法。

关联题

• 同套路：41. 缺失的第一个正数 —— 同款”下标即哈希”，它是本题的困难版
• 进阶：442. 数组中重复的数据 —— 同套路改问”谁出现了两次”
• 知识点：值域限定在 [1, n] 是原地哈希成立的前提；看到”O(1) 空间找缺失/重复”先确认值域