我来给你讲解 LeetCode 第 448 题：找到所有数组中消失的数字。

题目描述

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

要求：时间复杂度为 O(n)，空间复杂度为 O(1)（不考虑返回结果的数组）。

示例：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
解释：数组长度为8，应包含数字1-8，但缺少5和6

解题思路分析

第一步：理解问题核心

数组长度为 n，数字范围是 1 到 n，有些数字可能出现多次，有些数字可能缺失。我们需要找出所有缺失的数字。

第二步：思考基础解法

最直接的想法是使用哈希表：

• 遍历数组，记录每个数字是否出现
• 再次遍历 1 到 n，检查哪些数字没出现
  但这样空间复杂度是 O(n)，不满足要求。

第三步：利用现有数组空间

既然要求 O(1) 额外空间，我们可以利用数组 nums 本身来记录信息。关键思路是：用数组索引作为数字的标识。

具体方法：对于每个数字 nums[i]，我们将索引为 abs(nums[i]) - 1 的位置标记为负数，表示这个数字出现过。

第四步：详细步骤分解

步骤 1：标记出现过的数字

• 遍历数组，对于每个数字 x = nums[i]
• 计算索引 index = abs(x) - 1（减1是因为数组索引从0开始）
• 将 nums[index] 标记为负数（如果已经是负数则保持）

步骤 2：收集缺失的数字

• 再次遍历数组，对于索引 i
• 如果 nums[i] > 0，说明数字 i + 1 没有出现过
• 将这些数字加入结果列表

第五步：完整算法演示

以示例 [4,3,2,7,8,2,3,1] 为例：

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

• i=0: nums[0]=4 → index=3 → nums[3]=7变为-7 → [4,3,2,-7,8,2,3,1]
• i=1: nums[1]=3 → index=2 → nums[2]=2变为-2 → [4,3,-2,-7,8,2,3,1]
• i=2: nums[2]=-2 → abs=2 → index=1 → nums[1]=3变为-3 → [4,-3,-2,-7,8,2,3,1]
• i=3: nums[3]=-7 → abs=7 → index=6 → nums[6]=3变为-3 → [4,-3,-2,-7,8,2,-3,1]
• i=4: nums[4]=8 → index=7 → nums[7]=1变为-1 → [4,-3,-2,-7,8,2,-3,-1]
• i=5: nums[5]=2 → index=1 → nums[1]已经是负数，保持不变
• i=6: nums[6]=-3 → abs=3 → index=2 → nums[2]已经是负数，保持不变
• i=7: nums[7]=-1 → abs=1 → index=0 → nums[0]=4变为-4 → [-4,-3,-2,-7,8,2,-3,-1]

第二次遍历（收集结果）：

• 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缺失！
• i=5: nums[5]=2 > 0 → 数字6缺失！
• i=6: nums[6]=-3 < 0 → 数字7出现过
• i=7: nums[7]=-1 < 0 → 数字8出现过

结果：[5, 6]

第六步：代码实现要点

def findDisappearedNumbers(nums):
    # 第一次遍历：标记出现过的数字
    for i in range(len(nums)):
        index = abs(nums[i]) - 1  # 计算对应的索引位置
        if nums[index] > 0:       # 如果还没被标记过
            nums[index] = -nums[index]  # 标记为负数
    
    # 第二次遍历：收集缺失的数字
    result = []
    for i in range(len(nums)):
        if nums[i] > 0:           # 正数表示该位置对应的数字缺失
            result.append(i + 1)
    
    return result

第七步：复杂度分析

• 时间复杂度：O(n)，两次线性遍历
• 空间复杂度：O(1)（不考虑返回结果的空间）

第八步：关键技巧总结

这个算法的核心技巧是原地哈希，利用数组索引本身来记录信息，通过正负号标记是否出现过，既完成了信息记录又没有使用额外空间。

这种方法在解决类似"找出缺失/重复数字"的问题时非常有用，是面试中的常见技巧。