文章目录
- 摘要
- 描述
- 题解答案（直觉方法）
- 题解代码（Swift 可运行 Demo）
- 题解代码分析
- 为什么要用“负数标记”？
- 为什么需要用 `abs(nums[i])`？
- 第二轮遍历为什么能找到缺失值？
- 示例测试及结果
- 示例 1
- 示例 2
- 时间复杂度
- O(n)
- 空间复杂度
- O(1) 额外空间
- 总结
- “用符号（正负）作为额外标记信息”的技巧
摘要
这题可以说是数组题里最典型的“原地标记法”应用之一。题目要求我们找出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必定存在。
我们可以利用“把出现过的数字对应的位置标记为负数”这种方式，把数组本身变成一个“出现记录表”。
整体思路：
遍历数组，对于每个数字
x- 我们让数组中
x-1的位置变成负数（如果还没负）
- 我们让数组中
遍历标记后的数组
- 所有仍然是正数的位置
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 标记
在实际业务逻辑中，这种技巧也能用于：
- 用户状态表中“是否访问过”的标记（即使在共享数据结构中）
- 工具链中处理序列时进行轻量级标记
- 内存敏感场景的原地修改技巧
