LeetCode 第 448 题：找到所有数组中消失的数字 题目描述 给定一个长度为 n 的整数数组 nums ，数组中的元素范围在 [1, n] 之间。由于数组长度是 n ，而元素范围是 1 到 n ，所以理论上每个数字都应该恰好出现一次。但是，由于某些原因，有些数字可能出现两次，而有些数字则消失了。你的任务是找出所有在 [1, n] 范围内，但没有出现在数组中的数字。 要求： 在不使用额外空间（即空间复杂度为 O(1)）且时间复杂度为 O(n) 的情况下完成。 你可以假定返回的列表不算在额外空间内。 示例： 输入： nums = [4,3,2,7,8,2,3,1] 输出： [5,6] 解释：数组长度为 8，元素范围应为 [ 1,8 ]。数字 5 和 6 没有出现。 解题过程 这个问题的一个直观解法是使用一个哈希集合（HashSet）来记录所有出现过的数字，然后遍历 1 到 n，检查哪个数字不在集合中。但这种方法需要 O(n) 的额外空间，不符合题目对空间复杂度的要求。 我们的目标是利用数组本身作为哈希表，通过标记来记录哪些数字出现过。由于数组索引的范围是 [0, n-1] ，而数字的范围是 [1, n] ，我们可以建立一个巧妙的映射关系。 步骤 1：理解核心思想——原地哈希 我们可以将数组的索引与数字的值关联起来。具体来说： 对于一个数字 x ，它应该出现在数组的 x-1 这个索引位置上。 例如，数字 1 应该出现在索引 0 ，数字 2 应该出现在索引 1 ，...，数字 n 应该出现在索引 n-1 。 我们的策略是：遍历数组，对于每个遇到的数字 x ，我们去标记索引为 |x| - 1 的位置，表示数字 |x| 已经出现过。这里取绝对值是因为我们后续可能会修改数组元素的值。 步骤 2：设计标记方法 如何在不丢失原始信息的情况下进行标记呢？一个巧妙的方法是 将对应索引位置的数字变成负数 。 过程如下： 遍历数组 nums 中的每一个元素 num 。 计算 num 所对应的索引： index = |num| - 1 。 注意： num 可能已经被我们标记为负数，所以要用绝对值 |num| 来确保索引计算正确。 将 nums[index] 的值设置为其本身的负数（如果它已经是负数，则保持不变）。 例如，如果 nums[index] 是 5，我们就把它变成 -5。 这个操作意味着：数字 |num| 已经出现过了。 步骤 3：遍历并标记 让我们用示例 nums = [4,3,2,7,8,2,3,1] 来一步步演示这个过程。 初始数组： [4, 3, 2, 7, 8, 2, 3, 1] i=0, num = 4 : 对应索引 index = |4| - 1 = 3 将 nums[3] (7) 变为负数： nums[3] = -7 数组变为： [4, 3, 2, -7, 8, 2, 3, 1] i=1, num = 3 : 对应索引 index = |3| - 1 = 2 将 nums[2] (2) 变为负数： nums[2] = -2 数组变为： [4, 3, -2, -7, 8, 2, 3, 1] i=2, num = -2 : 注意这里 num 是负数，我们取绝对值： | -2 | = 2 对应索引 index = 2 - 1 = 1 将 nums[1] (3) 变为负数： nums[1] = -3 数组变为： [4, -3, -2, -7, 8, 2, 3, 1] i=3, num = -7 : 取绝对值： | -7 | = 7 对应索引 index = 7 - 1 = 6 将 nums[6] (3) 变为负数： nums[6] = -3 数组变为： [4, -3, -2, -7, 8, 2, -3, 1] i=4, num = 8 : 对应索引 index = 8 - 1 = 7 将 nums[7] (1) 变为负数： nums[7] = -1 数组变为： [4, -3, -2, -7, 8, 2, -3, -1] i=5, num = 2 : 对应索引 index = 2 - 1 = 1 nums[1] 已经是负数 (-3)，保持不变。 数组不变： [4, -3, -2, -7, 8, 2, -3, -1] i=6, num = -3 : 取绝对值： | -3 | = 3 对应索引 index = 3 - 1 = 2 nums[2] 已经是负数 (-2)，保持不变。 数组不变： [4, -3, -2, -7, 8, 2, -3, -1] i=7, num = -1 : 取绝对值： | -1 | = 1 对应索引 index = 1 - 1 = 0 将 nums[0] (4) 变为负数： nums[0] = -4 最终数组： [-4, -3, -2, -7, 8, 2, -3, -1] 步骤 4：找出消失的数字 标记完成后，我们再次遍历数组。这次我们看每个索引 i （从 0 到 n-1）： 如果 nums[i] 的值是 正数 ，说明从来没有一个数字 x 使得 |x| - 1 = i 。换句话说，数字 i+1 从来没有出现过。 如果 nums[i] 的值是 负数 ，说明数字 i+1 出现过。 分析我们的最终数组 [-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] 。 步骤 5：算法总结与代码思路 第一次遍历（标记阶段） ： 对于数组中的每个元素 num ，计算 index = |num| - 1 。 如果 nums[index] 是正数，将其变为负数，表示数字 |num| 出现过。 第二次遍历（收集结果阶段） ： 遍历索引 i 从 0 到 n-1。 如果 nums[i] 仍然是正数，说明数字 i+1 是消失的数字，将其加入结果列表。 这个算法只遍历了数组两次，时间复杂度是 O(n)。除了结果列表，我们没有使用额外的数据结构，空间复杂度是 O(1)（结果列表不计入空间复杂度）。