（LeetCodeHot100）448. 找到所有数组中消失的数字——find-all-numbers-disappeared-in-an-array

zhangzhang2025-11-132025-11-13

448. 找到所有数组中消失的数字——find-all-numbers-disappeared-in-an-array

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

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

示例 2：

1 2	输入：nums = [1,1] 输出：[2]

提示：

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n

我的正确答案

将1-n先存放进哈希表，把有的删掉，没有的就是消失的数字

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        Set<Integer> set = new HashSet<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= nums.length; i++) {
            set.add(i);
        }
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])){
                set.remove(nums[i]);
            }
        }
        Iterator<Integer> it = set.iterator();
        while (it.hasNext()) {
            int res = it.next();
            result.add(res);
        }
        return result;
    }
}

但是复杂度太高：

执行用时分布
34ms
击败5.07%

消耗内存分布
80.63MB
击败5.04%

官方答案方法：原地修改

思路及解法

（没有的数就不会被加n，最后遍历的时候就会小于等于n）

这个解法的核心是利用原数组原地标记数字的存在性，从而将空间复杂度优化到 O(1)，具体思路拆解如下：

一、核心痛点：如何不额外申请空间记录 “存在的数字”？

题目中数字范围是 [1, n]，而数组长度恰好是 n。这意味着：

数组的索引范围 [0, n-1] 可以和数字 [1, n] 一一对应（索引 i 对应数字 i+1）。

我们可以用数组本身的元素来标记 “对应数字是否存在”—— 通过修改元素值（让其超出 [1, n] 范围）来表示 “存在”，未被修改的元素则对应 “缺失的数字”。

二、具体操作：用 “加 n” 标记存在性

步骤 1：遍历数组，标记已出现的数字

对于数组中的每个数字 x（注意可能已被修改，需先还原）：

它对应的索引是 x-1（因为数字 x 对应索引 x-1）。
我们将 nums[x-1] 的值加上 n（因为原数组元素都 ≤ n，加 n 后必然 > n，可作为 “已存在” 的标记）。

步骤 2：遍历数组，寻找未被标记的索引

再次遍历数组，对于每个索引 i：

若 nums[i] ≤ n：说明该位置从未被标记，即数字 i+1 从未出现过（是缺失的数字）。
若 nums[i] > n：说明数字 i+1 存在（已被标记）。

三、关键细节：如何处理 “已被修改的数字”？

第一次遍历时，可能遇到已经被 “加过 n” 的数字（例如重复出现的数字）。此时需要先通过 x % n 还原出它本来的值（因为 x 原本 ≤ n，加 n 后 x % n 就是原数）。

四、示例演示（以 `nums = [4,3,2,7,8,2,3,1]`，`n=8` 为例）

步骤 1：标记存在的数字

遍历每个元素 x，计算原数 x % n（这里所有数初始 ≤8，所以 x%n = x），再标记对应索引：
- x=4 → 索引 3 → nums[3] = 7 + 8 = 15
- x=3 → 索引 2 → nums[2] = 2 + 8 = 10
- x=2 → 索引 1 → nums[1] = 3 + 8 = 11
- x=7 → 索引 6 → nums[6] = 3 + 8 = 11
- x=8 → 索引 7 → nums[7] = 1 + 8 = 9
- x=2 → 索引 1 → nums[1] = 11 + 8 = 19（已标记过，再加 8）
- x=3 → 索引 2 → nums[2] = 10 + 8 = 18（已标记过，再加 8）
- x=1 → 索引 0 → nums[0] = 4 + 8 = 12
标记后数组变为：[12, 19, 18, 15, 8, 2, 11, 9]

步骤 2：寻找缺失的数字

遍历数组，检查每个元素是否 ≤8：

索引 0：12 >8 → 数字 1 存在
索引 1：19 >8 → 数字 2 存在
索引 2：18 >8 → 数字 3 存在
索引 3：15 >8 → 数字 4 存在
索引 4：8 ≤8 → 数字 5 缺失（加入结果）
索引 5：2 ≤8 → 数字 6 缺失（加入结果）
索引 6：11 >8 → 数字 7 存在
索引 7：9 >8 → 数字 8 存在

最终结果：[5,6]，符合预期。

五、总结

核心思想：用原数组的索引对应数字 [1,n]，通过 “加 n” 标记数字存在，未被标记的索引对应缺失数字。
优势：无需额外空间（空间复杂度 O(1)），时间复杂度 O(n)（两次遍历数组）。
关键操作：第一次遍历用 x % n 还原数字，再标记；第二次遍历检查元素是否 ≤n 来判断缺失。

n，能否让 nums 充当哈希表呢？

由于 nums 的数字范围均在 [1,n] 中，我们可以利用这一范围之外的数字，来表达「是否存在」的含义。

具体来说，遍历 nums，每遇到一个数 x，就让 nums[x−1] 增加 n。由于 nums 中所有数均在 [1,n] 中，增加以后，这些数必然大于 n。最后我们遍历 nums，若 nums[i] 未大于 n，就说明没有遇到过数 i+1。这样我们就找到了缺失的数字。

注意，当我们遍历到某个位置时，其中的数可能已经被增加过，因此需要对 n 取模来还原出它本来的值。

代码

class Solution {
public:
    const int mod = 998244353;
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        for (auto& num : nums) {
            int x = (num - 1) % n;
            if (nums[x] <= n) {
                nums[x] += n;
            }
        }
        vector<int> ret;
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                ret.push_back(i + 1);
            }
        }
        return ret;
    }
};