LeetCode 448 - 找到所有数组中消失的数字

摘要

这题可以说是数组题里最典型的“原地标记法”应用之一。题目要求我们找出1...n中没出现过的数字，而且还给了个进阶要求：在 O(n) 时间、O(1) 额外空间内完成。

听起来好像有点限制，但只要利用“数组本身可作为标记空间”的特性，就能用非常干净利落的方式解决。这类技巧专项训练非常重要，因为真实开发中有很多场景都可以借鉴这种思路。

描述

输入是一个长度为n的数组，里面的每个数字都在[1, n]区间内。我们要返回所有没有出现在数组里的数字。

比如：

nums = [4,3,2,7,8,2,3,1] 缺失的是：5 和 6

或者：

nums = [1,1] 缺失的是：2

进阶要求我们不能使用额外空间（返回结果除外），也就是说不能随便用哈希表、map 之类的辅助结构。

题解答案（直觉方法）

利用这样一个事实：

数组中的值都在[1, n]范围内，那么每个值x对应数组位置x-1必定存在。

我们可以利用“把出现过的数字对应的位置标记为负数”这种方式，把数组本身变成一个“出现记录表”。

整体思路：

1. 遍历数组，对于每个数字x

   • 我们让数组中x-1的位置变成负数（如果还没负）

2. 遍历标记后的数组

   • 所有仍然是正数的位置i，说明数字i+1没出现过

这是典型的“使用符号作为标记”的技巧。

题解代码（Swift 可运行 Demo）

importFoundationclassSolution{funcfindDisappearedNumbers(_nums:[Int])->[Int]{varnums=nums// 复制一份，便于原地修改letn=nums.count// 第一步：把出现过的数字对应位置标记成负数foriin0..<n{letindex=abs(nums[i])-1ifnums[index]>0{nums[index]=-nums[index]}}// 第二步：正数的位置就是缺失的数字varresult=[Int]()foriin0..<n{ifnums[i]>0{result.append(i+1)}}returnresult}}// MARK: - Demoletsolution=Solution()print("示例 1：",solution.findDisappearedNumbers([4,3,2,7,8,2,3,1]))// [5, 6]print("示例 2：",solution.findDisappearedNumbers([1,1]))// [2]

题解代码分析

为什么要用“负数标记”？

这是这题最精妙的地方。

• 数组长度为 n
• 所有数字范围都在1...n

那么数字和索引之间刚好可以一一映射。

例子：

数字 4 —— 对应索引 3 数字 1 —— 对应索引 0 数字 7 —— 对应索引 6

利用这点，我们可以把“某个数字出现过”这件事记录到nums[x-1]中。

最简单的标记方式就是：

→把 nums[x-1] 变成负数

负数代表“已经被访问过了”。

为什么不直接改成 0 或者某个标志值？

因为之后我们仍然需要判断原本的值，而负数保留了数值本身的信息，且不会和[1,n]冲突。

为什么需要用abs(nums[i])？

因为标记过程中，有些位置已经变成负数了，所以必须取绝对值。

第二轮遍历为什么能找到缺失值？

因为：

• 出现过的数字对应位置已经被标记为负数
• 没出现过的位置仍然是正数

所以：

第 i 个位置是正数 → i + 1 没出现过

就是缺失值。

示例测试及结果

我们用题目给的例子跑一下：

示例 1

输入： [4,3,2,7,8,2,3,1] 中间标记过程如下： 原始： 4 3 2 7 8 2 3 1 标记后： -4 -3 -2 -7 8 -2 -3 -1 ↑ ↑ 正 正 缺失数字为：[5, 6]

示例 2

输入： [1,1] 标记后：[-1, 1] 缺失的是 2

运行 Demo 即可得到相同结果。

时间复杂度

O(n)

• 一次遍历标记出现过的数字
• 一次遍历找出没被标记的位置
• 两次线性扫描，总共 O(n)

在大数据量下仍然非常稳定。

空间复杂度

O(1) 额外空间

注意：返回的结果数组不算额外空间。

其余操作都在原数组上原地完成，不需要新开结构。

总结

这题真正想让你掌握的是：

“用符号（正负）作为额外标记信息”的技巧

它在很多 O(1) 空间的题里都能出现，比如：

• 找重复数字
• 找缺失数字
• 数组原地哈希
• 原地 bucket 标记

在实际业务逻辑中，这种技巧也能用于：

• 用户状态表中“是否访问过”的标记（即使在共享数据结构中）
• 工具链中处理序列时进行轻量级标记
• 内存敏感场景的原地修改技巧