问题描述

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

解题思路

本题的核心难点在于要求 O(n) 时间复杂度和 O(1) 额外空间（返回列表不计入额外空间）。常规的哈希表做法需要 O(n) 空间，不符合要求。

原地哈希（标记法）

元素的值范围是 [1, n]，恰好对应数组索引 [0, n-1]。利用这个特性，我们可以在原数组上进行”标记”：

  1. 第一次遍历 —— 标记出现过数字对应的索引：

    • 对于每个元素 nums[i]，取其绝对值得到原值 val
    • 计算索引 index = val - 1
    • 将 nums[index] 变为负数（取反），表示”数字 val 已经出现过”
    • 注意使用 Math.abs() 取绝对值，因为元素可能已经被之前的标记操作变成了负数

  2. 第二次遍历 —— 收集缺失的数字：

    • 遍历数组，如果 nums[i] > 0（仍为正数），说明数字 i + 1 没有出现过
    • 将所有正数位置的索引 + 1 收集到结果列表中

举例说明

以输入 nums = [4, 3, 2, 7, 8, 2, 3, 1]（n=8）为例：

第一次遍历：

i nums[i] val(abs) index 标记前 nums[index] 标记后 nums
0 4 4 3 7 [4,3,2,-7,8,2,3,1]
1 3 3 2 2 [4,3,-2,-7,8,2,3,1]
2 -2 2 1 3 [4,-3,-2,-7,8,2,3,1]
3 -7 7 6 3 [4,-3,-2,-7,8,2,-3,1]
4 8 8 7 1 [4,-3,-2,-7,8,2,-3,-1]
5 2 2 1 -3 已在步骤2标记，无变化
6 -3 3 2 -2 已标记，无变化
7 -1 1 0 4 [-4,-3,-2,-7,8,2,-3,-1]

第二次遍历：nums[4]=8>0 和 nums[5]=2>0，所以缺失数字为 4+1=5 和 5+1=6。

结果：[5, 6]

核心思想

通过将元素值映射为数组索引，并用符号位（正负号）作为”标记”，在不消耗额外空间的前提下实现了哈希集合的功能。这是空间压缩的经典技巧。

复杂度分析

  • 时间复杂度：O(n)，两次遍历数组。
  • 空间复杂度：O(1)，仅使用常数额外空间（返回列表不计入）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package code.J448;

import java.util.ArrayList;
import java.util.List;

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