LeetCode 第 448 题：找到所有数组中消失的数字

题目描述

给定一个长度为 n 的整数数组 nums，数组中的元素范围在 [1, n] 内。找出所有在 [1, n] 范围内，但没有出现在 nums 中的数字。

要求：

• 你能在不使用额外空间（即空间复杂度为 O(1)）且时间复杂度为 O(n) 的情况下解决这个问题吗？你可以假定返回的列表不算在额外空间内。

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

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

解题过程循序渐进讲解

第一步：理解问题与约束条件

这个问题的核心是，我们有一个长度为 n 的数组，里面的数字理论上应该是从 1 到 n 各出现一次。但实际情况是，有些数字可能出现了两次或更多次，这就导致另一些在 1 到 n 范围内的数字完全没有出现。我们的任务就是找出这些“消失”的数字。

最大的挑战在于题目要求：时间复杂度 O(n)，空间复杂度 O(1)（除了返回的列表）。这意味着我们不能使用额外的数据结构（如哈希表）来记录哪些数字出现过。

第二步：思考基础思路（非最优解，用于理解）

如果不考虑空间复杂度的限制，最直观的解法是使用一个哈希集合（HashSet）：

1. 创建一个空的哈希集合 seen。
2. 遍历数组 nums，将每个数字添加到 seen 中。
3. 再次遍历从 1 到 n 的数字，检查每个数字是否在 seen 中。如果不在，则将其加入结果列表。

这种方法的时间复杂度是 O(n)，但空间复杂度也是 O(n)，因为我们需要一个额外的集合来存储出现过的数字。这不符合题目的进阶要求。

第三步：利用数组本身作为标记（核心思路）

为了达到 O(1) 的空间复杂度，我们需要巧妙地利用给定的数组 nums 本身来记录信息。关键观察点是：

• 数组 nums 的长度是 n。
• 数组 nums 中的元素值都在 [1, n] 范围内。

这意味着，数组的索引（从 0 到 n-1）和数组元素可能出现的值（从 1 到 n）存在一种对应关系：值 - 1 = 索引。

我们可以利用这种对应关系，通过修改原数组来标记某个数字是否出现过。具体思路是：遍历数组，对于每个遇到的数字 x，我们将它对应的索引位置（即 x-1）上的数字做一个“标记”，表示数字 x 出现过。

第四步：设计标记策略

如何做标记，而又不丢失原始信息呢？一个巧妙的方法是：将对应位置上的数字变成负数。

具体步骤分解：

1. 遍历数组 nums 中的每一个数字。
2. 对于当前数字 num，我们计算它应该对应的索引：index = abs(num) - 1。这里使用 abs（绝对值）是因为在标记过程中，我们可能会将某些数字变为负数，但我们需要的是它原始的值所对应的索引。
3. 找到索引 index 后，我们检查 nums[index] 的值：
   • 如果 nums[index] 是正数，我们将其变为负数。这表示“数字 index + 1 出现过一次”。
   • 如果 nums[index] 已经是负数，我们就不做任何操作（或者可以再次取负，但通常保持负数即可），因为它已经被标记过了。
4. 完成整个数组的遍历和标记后，我们再次遍历数组。这次，我们看每个索引 i（从 0 到 n-1）对应的值 nums[i]：
   • 如果 nums[i] 仍然是正数，这说明什么？这说明在整个过程中，没有任何一个数字指向过索引 i。换句话说，数字 i + 1 从来没有在数组中出现过！因此，数字 i + 1 就是一个“消失的数字”。
5. 将所有满足 nums[i] > 0 的 i+1 收集起来，就是最终的答案。

第五步：通过示例逐步推演

让我们用示例 nums = [4, 3, 2, 7, 8, 2, 3, 1] (n=8) 来走一遍流程。

第一次遍历（标记过程）：

1. 遇到 num = 4 -> index = 4-1 = 3 -> nums[3] 是 7（正数） -> 标记为 -7。数组变为: [4, 3, 2, -7, 8, 2, 3, 1]
2. 遇到 num = 3 -> index = 3-1 = 2 -> nums[2] 是 2（正数） -> 标记为 -2。数组变为: [4, 3, -2, -7, 8, 2, 3, 1]
3. 遇到 num = 2 -> index = 2-1 = 1 -> nums[1] 是 3（正数） -> 标记为 -3。数组变为: [4, -3, -2, -7, 8, 2, 3, 1]
4. 遇到 num = 7 -> index = 7-1 = 6 -> nums[6] 是 3（正数） -> 标记为 -3。数组变为: [4, -3, -2, -7, 8, 2, -3, 1]
5. 遇到 num = 8 -> index = 8-1 = 7 -> nums[7] 是 1（正数） -> 标记为 -1。数组变为: [4, -3, -2, -7, 8, 2, -3, -1]
6. 遇到 num = 2 -> index = 2-1 = 1 -> nums[1] 是 -3（负数，已标记过） -> 保持不变。
7. 遇到 num = 3 -> index = 3-1 = 2 -> nums[2] 是 -2（负数，已标记过） -> 保持不变。
8. 遇到 num = 1 -> index = 1-1 = 0 -> nums[0] 是 4（正数） -> 标记为 -4。数组变为: [-4, -3, -2, -7, 8, 2, -3, -1]

标记完成后的数组：[-4, -3, -2, -7, 8, 2, -3, -1]

第二次遍历（寻找消失的数字）：
我们遍历索引 0 到 7，检查 nums[i] 的符号。

• i=0: nums[0] = -4 (<0) -> 数字 1 出现过。
• i=1: nums[1] = -3 (<0) -> 数字 2 出现过。
• i=2: nums[2] = -2 (<0) -> 数字 3 出现过。
• i=3: nums[3] = -7 (<0) -> 数字 4 出现过。
• i=4: nums[4] = 8 (>0) -> 数字 5 没有出现过！将 5 加入结果。
• i=5: nums[5] = 2 (>0) -> 数字 6 没有出现过！将 6 加入结果。
• i=6: nums[6] = -3 (<0) -> 数字 7 出现过。
• i=7: nums[7] = -1 (<0) -> 数字 8 出现过。

最终结果：[5, 6]，与示例一致。

第六步：代码实现（关键部分解释）

以下是基于上述思路的 Python 代码实现：

def findDisappearedNumbers(nums):
    # 第一次遍历：进行标记
    for num in nums:
        # 获取当前数字应对应的索引。使用绝对值是因为数字可能已被标记为负。
        index = abs(num) - 1
        # 如果该索引位置的数是正数，将其标记为负数（表示这个索引对应的数字出现过）
        if nums[index] > 0:
            nums[index] = -nums[index]
    
    result = []
    # 第二次遍历：收集结果
    for i in range(len(nums)):
        # 如果当前索引位置的数还是正数，说明数字 (i+1) 没有出现过
        if nums[i] > 0:
            result.append(i + 1)
    return result

第七步：复杂度分析

• 时间复杂度：O(n)。我们进行了两次线性遍历，每次都是 O(n)。
• 空间复杂度：O(1)。除了返回结果的列表（题目说明不计入空间复杂度），我们没有使用任何额外的、大小与输入规模 n 相关的数据结构。我们只是原地修改了输入数组。

总结

这个算法的核心在于利用数组索引和元素值的天然映射关系，通过将元素取负数的方式来标记某个数字是否出现过，从而在不使用额外空间的情况下高效地解决了问题。这是一种典型的“原地哈希”或“符号标记”技巧，在处理类似范围的数组问题时非常有用。