企业官网建设流程全解析

我第一次刷这道题的时候，第一反应是“这还不简单？拿一个哈希集合，把所有出现过的数字丢进去，然后从 1 到 n 扫一遍，谁没出现谁就是答案”。十行代码写完，自我感觉良好。直到后来有人问我：“这题的空间复杂度是 O(n)，如果面试官要求你只能用 O(1) 的额外空间，你打算怎么改？”我一下子愣住了。

这道题就是力扣上的 Find All Numbers Disappeared in an Array，题号 448，在我自己的刷题笔记系列里正好排到第 101 篇。说句实话，它表面上看是一道非常基础的“找出缺失数字”问题，真正把它吃透之后，你会发现它背后藏着一个特别重要的思维模型——让数组本身代替哈希表。这个技巧一旦掌握，能帮你串起来一大批看似不相关的数组类题目。这篇文章我就把这道题从题目分析、核心思路、两种原地标记写法，到边界条件、同类题迁移，完整地梳理一遍，适合所有正在刷力扣、准备面试的朋友阅读。

1. 题面解析与三个“直觉但不达标”的方案

先看题目描述：给你一个长度为 n 的整数数组 nums，其中 nums[i] 的取值范围是 [1, n]（注意是闭区间，最小是 1，最大正好是 n）。在这个数组里，有的数字可能出现多次，有的数字一次都没出现。请你找出所有在 [1, n] 范围内但没有出现在数组中的数字，并以数组形式返回结果。

举个例子：输入 nums = [4,3,2,7,8,2,3,1]，长度 n = 8，但是 5 和 6 没有出现，所以答案是 [5,6]。

题目要求的是 O(n) 时间复杂度和 O(1) 额外空间复杂度。所谓“额外空间”，就是不把用来存答案的数组算进去，因为你总要返回一个结果列表，那个空间不算额外开销。真正要抠的是在找答案的过程中，除了原数组和返回结果之外，你还用了多少额外的存储。

我先把大家最容易想到的几个方案摆出来，看看它们各自卡在哪里。

1.1 哈希集合法：最简单，但空间不达标

用一个哈希集合记录所有出现过的数字，然后从 1 遍历到 n，检查哪个数字不在集合里，就把它加入答案。这个思路直白得不能再直白，代码也就不到十行：

def findDisappearedNumbers(nums): seen = set(nums) return [i for i in range(1, len(nums) + 1) if i not in seen]

时间复杂度是 O(n)，因为遍历一次数组 + 遍历一次 1 到 n。但空间复杂度是 O(n)，因为你在原数组之外又建了一个集合。对于这道题来说，这个方案是“好用但不达标”。如果面试官没提空间要求，用它完全没问题，但一旦限制 O(1) 额外空间，就不能这么写了。

1.2 排序法：时间先败下阵来

另一个思路是把数组排序，然后从头到尾扫一遍，看看哪些数字在 1 到 n 的范围内缺号。排序本身的时间复杂度是 O(n log n)，比 O(n) 要差一个档次。而且排序之后虽然可以在原数组上操作，但很多语言的排序实现会额外占用 O(log n) 甚至更多的栈空间或临时数组空间，严格来说也不算特别干净。

这道题要求的是“线性时间”，所以排序法在时间上就被淘汰了。

1.3 额外布尔数组法：换汤不换药

有些人会想，那我用一个长度为 n+1 的布尔数组，把出现过的数字对应位置标成 true，最后看哪一个是 false，不就行了？思路是对的，但额外用了一个 O(n) 的布尔数组，本质上和哈希集合的空间复杂度一样，依旧不符合要求。

这三种方案放在一起，你会发现问题非常清楚：我们需要的是一种“不建额外结构，原地记录信息，还不丢失原数组有用信息”的手段。能想通这一点，这道题的真正考点就开始浮出水面了。

2. 把数组当哈希表：值域与索引的映射是全题的总开关

题目为什么这么设计？因为数组的长度是 n，元素值的范围又恰好是 1 到 n，这两个数字之间存在着一种天然的一一对应关系：值 x 对应的位置是 x-1。

这句话就是整道题的总开关。你想一想，如果数组里出现了数字 3，那就说明索引 2 这个位置应该被“打个记号”；如果数组里出现了数字 7，那就说明索引 6 应该被打个记号。等所有记号打完之后，哪个位置没有记号，哪个位置对应的数字就是缺失的。

为什么能这么做？因为常规哈希表做的事情是“把键映射到存储桶”，而这道题的值域 [1, n] 本身就对应着长度为 n 的数组的索引 [0, n-1]，所以这个长度为 n 的数组天然就是一个“哈希表”，索引就是键，位置上的值就是状态位。我们不需要额外开空间，因为原来的数组本身就是那张哈希表。

这时候核心问题就变成了：你用什么方式在对应位置上“打记号”，而且不能把数组里的原始信息完全破坏掉。因为第一遍标记的过程中，你后面还要读取数组里其他元素的值，如果一轮走下来把数组里的数字全改了，后面就没办法正确遍历了。

于是就有了两大类思路，它们的本质完全一样，只是打记号的方式不同：

• 一种是利用数值的符号位，把正数变成负数，负数就代表“出现过”；
• 另一种是利用数值的大小，在原值基础上加上一个足够大的偏移量，超过阈值就代表“出现过”。

这两种方式都不会把原始信息彻底弄丢：取绝对值能还原原来的数，取模也能还原原来的数。这就是“原地标记”的精髓——在保存原始值的同时，用额外的状态维度记录信息。把它想成在图书馆的书上贴便签：你不撕掉书的封面，只是在上面贴个标记，以后还能把便签撕下来看清封面上的书名。

这种思维一旦建立，后面两套代码就非常容易理解了。

3. 原地标记法两种实现：取负法和偏移法逐行拆解

理论上我们已经知道目标是在对应索引位上打标记，现在就看具体怎么打。我强烈建议你把两种方法都亲手写一遍，因为它们在面试中出现的频率都很高，而且各自的细节坑不太一样。

3.1 取负法：利用符号位做标记

取负法的核心就一句话：如果某个数字 x 出现过，就把 nums[x-1] 变成负数；第二次遍历时，哪个位置还是正数，哪个位置对应的数字就是缺失的。

def findDisappearedNumbers(nums): n = len(nums) for i in range(n): idx = abs(nums[i]) - 1 if nums[idx] > 0: nums[idx] = -nums[idx] return [i + 1 for i in range(n) if nums[i] > 0]

这短短几行代码里藏着三个非常容易写错的地方。

第一，必须对当前元素取绝对值。因为在你遍历的过程中，当前遍历到的 nums[i] 可能已经被前面某一次标记改成了负数。比如数组 [4,3,2,7,8,2,3,1]，当你走到 i=2 的时候，nums[2] 已经因为前面的数字 3 而被标记成了 -2？不对，我们来仔细走一遍。如果前面遍历到 3，那么 idx=2，nums[2] 会被标记成负数。所以当你后续再走到索引 2 这个位置时，取到的值就是负数。如果你直接用这个负数去算索引，比如 nums[i] = -2，那 idx = -2 - 1 = -3，直接数组越界。所以取绝对值这一步，本质上是“从打满标记的数组中读取原始值”。

第二，打标记时一定要先判断if nums[idx] > 0。为什么不能写成nums[idx] = -nums[idx]直接取反？因为数组里有重复数字。假设 2 出现了两次，第一次遇到 2 时，nums[1] 从正数被变成负数；第二次再遇到 2 时，如果不加判断直接把 nums[1] 取反，它又从负数变回正数了。这样第一遍标记等于没标记，最后你会误判数字 2 是缺失的。所以必须判断，如果这个位置还是正数才标记；如果它已经是负数，说明这个数字之前已经出现过，不需要也不能再操作。

第三，最后扫描时，nums[i] > 0的位置对应数字 i+1 就是缺失的。因为出现过的数字都把对应位置变成负数了，没被碰过的位置自然保持初始正数。这种方法的题解在力扣评论区很常见，但能一次写对的人其实并不多，问题基本都出在绝对值上。

用一个具体例子验证一下取负法的过程。nums = [4,3,2,7,8,2,3,1]：

• i=0，取 nums[0]=4，idx=3，nums[3]=7 变成 -7；
• i=1，取 nums[1]=3，idx=2，nums[2]=2 变成 -2；
• i=2，取 nums[2]=-2，abs 之后是 2，idx=1，nums[1]=3 变成 -3；
• i=3，取 nums[3]=-7，abs 之后是 7，idx=6，nums[6]=3 变成 -3；
• i=4，取 nums[4]=8，idx=7，nums[7]=1 变成 -1；
• i=5，取 nums[5]=2，abs 之后是 2，idx=1，nums[1] 已经是 -3，不动；
• i=6，取 nums[6]=-3，abs 之后是 3，idx=2，nums[2] 已经是 -2，不动；
• i=7，取 nums[7]=-1，abs 之后是 1，idx=0，nums[0]=4 变成 -4。

最终数组变成 [-4, -3, -2, -7, -8, -2, -3, -1]，第二遍扫描发现索引 4 和索引 5（0-based）对应的 nums[4]=-8、nums[5]=-2 都是负数，不对，等一下，我们看第二遍扫描是要找正数？这个例子最后全是负数，那为什么答案还是 [5,6]？因为题目给的输入里 5 和 6 确实没出现过，它们对应的位置应该保持正数，但这里 nums[4] 被数字 8 标记成负数了呀——它标记的是索引 7 啊。我重新检查一下：原数组 [4,3,2,7,8,2,3,1]，数字 8 对应 idx=7，所以 nums[7] 变成负数。那么哪些位置没被标记成负数？我们看每个数字对应的 idx：

• 数字 4 -> idx=3，nums[3] 变负；
• 数字 3 -> idx=2，nums[2] 变负；
• 数字 2 -> idx=1，nums[1] 变负；
• 数字 7 -> idx=6，nums[6] 变负；
• 数字 8 -> idx=7，nums[7] 变负；
• 数字 2 -> idx=1，已负，不动；
• 数字 3 -> idx=2，已负，不动；
• 数字 1 -> idx=0，nums[0] 变负。

所以最终变了负号的位置是 0、1、2、3、6、7，而索引 4 和索引 5 对应的 nums[4]=8、nums[5]=2 都是正数！我刚才口算的时候把数组里的值记混了。这个例子正好说明了：真正保持正数的两个位置，就是缺失数字 5 和 6 的索引位 4 和 5。这恰好验证了整道题的逻辑，也提醒我们，这种过程最好自己拿笔走一遍，光看代码容易把索引和值绕晕。

3.2 偏移法：把数值整体抬高，避免符号判断的麻烦

取负法虽然有效，但总有人觉得处理绝对值麻烦，那就可以试试偏移法。核心思路是：如果某个数字 x 出现过，就在 nums[x-1] 这个位置的原值基础上加上 n。由于原数组所有元素都在 [1, n] 范围内，加上 n 之后，只要一个位置的值大于 n，就说明这个位置被标记过；而通过取模 n，我们总能还原出最开始的原始值。

def findDisappearedNumbers(nums): n = len(nums) for i in range(n): idx = (nums[i] - 1) % n nums[idx] += n return [i + 1 for i in range(n) if nums[i] <= n]

这里有个非常关键的理解点：我们在第一遍循环里修改了数组，后续循环中再读到 nums[i] 时，它可能已经不是原始值了。比如一个位置的原始值是 3，被标记一次后变成 3+n，再被标记一次变成 3+2n。那(nums[i] - 1) % n还能不能还原出原始索引？可以。因为 3 + kn 减去 1 之后，对 n 取模，kn 那一整项都会变成 0，剩下的就是 (3-1) % n，也就是原始值对应的索引。这就是偏移法能成立的根本原因：取模操作把加上的偏移量完整剥离掉了，所以即使某个位置被重复标记很多次，我们依然能获取原始信息，不会发生索引混乱。

再解释一下为什么要加 n 而不是加 1。假如你只加 1，那么一个位置被标记两次，值从原始值变成原始值+2；第二遍判断的时候，你会想用“如果等于某个特定值就认为没出现”，但多次标记累加之后你很难统一判断。比如原始值 1，标记两次变成 3，此时它到底是“没出现的 1”还是“出现过的 3”？根本说不清。加 n 的好处是，只要标记过一次，值就立刻超过 n，之后无论标记多少次，你只需要判断“是否大于 n”就能得到结果，互不干扰。这和取负法里用“是否小于 0”来判断是同一个道理。

3.3 两种方法怎么选：从面试表达和工程场景两个角度看

这两种方法的时间复杂度都是 O(n)，空间复杂度都是 O(1)，没有性能差异。它的差别主要在写法习惯和边界容错上。

我个人的经验是：面试时优先用取负法讲思路，因为它直观，面试官一听就懂；实际写题时更爱用偏移法，因为循环体里少了一个 if 分支，代码短，写起来更快。但如果你用 Java 或 C++ 做题，偏移法要注意数值溢出的问题。比如 n 很大，某个位置恰好被标记了几百次，累加的值可能超过 int 范围。虽然力扣的测试数据一般不会卡这个，但养成好习惯总是没坏处。取负法就不存在溢出问题，只是多几行判断。

4. 实战中的踩坑记录与边界用例复盘

这道题看起来简单，真正上手写的时候，坑比想象中多得多。我把自己刷题过程中踩过、以及帮别人 review 代码时见过的典型错误整理一下，每一条都是实际会发生的。

4.1 踩坑一：取负法漏掉 abs，导致数组越界

这是最经典的一个错误。

# 错误版本 for i in range(n): idx = nums[i] - 1 # 如果 nums[i] 已经是负数，idx 就是负数 nums[idx] = -nums[idx]

你可能会说：“我第一遍遍历的时候，当前位置的值还没被改过，怎么会是负数呢？”问题就出在数组里的数字是乱序的。假设 nums = [2, 1]：i=0 时，nums[0]=2，idx=1，把 nums[1] 变成 -1；i=1 时，当前位置 nums[1] 已经被上一轮改成了 -1，如果你不取绝对值，idx = -1 - 1 = -2，数组直接越界。所以记住一句话：凡是可能被改动的数组，遍历时读值第一件事永远是恢复原始值。

4.2 踩坑二：重复元素把负数又改回正数

这是我见过最多的错误，也是最隐蔽的。

# 错误版本 for i in range(n): idx = abs(nums[i]) - 1 nums[idx] = -nums[idx] # 直接取反，没有判断正负

用 nums = [2, 2] 测试：i=0，idx=1，nums[1]=2 变成 -2；i=1，idx=1，nums[1]=-2 又变成 2。好嘛，一轮下来，索引 1 又变回正数了。第二遍扫描时，你会以为数字 2 没出现过，白白冤枉它。所以打标记前必须判断目标位置是否还是正数，只有正数才需要变成负数。

4.3 踩坑三：偏移法的判断条件写错边界

偏移法第二遍扫描时，判断条件是nums[i] <= n还是nums[i] < n？这里差一个等于号，结果完全不同。如果原始数组里某个元素恰好等于 n，它在被标记一次之后，值会变成 2n；但如果它从来没被标记过，值就是 n。如果你写成< n，那些原始值正好等于 n 且恰好没出现在数组中的位置，会被误判成“已出现”，导致漏掉这个缺失数字。所以正确的判断是<= n，只要值小于等于 n，就说明这个位置从来没被标记过，对应数字缺失。

4.4 边界用例复盘：小数组里藏着大问题

推荐大家写完代码后，把这几个用例手动过一遍：

• n=1，nums = [1]：没有数字缺失，输出 []；
• nums = [1, 1]：缺少 2，输出 [2]；
• nums = [2, 2]：缺少 1，输出 [1]；
• nums = [3, 3, 3]：缺少 1 和 2，输出 [1, 2]；
• nums = [1, 2, 3, 4]：什么都不缺，输出 []；
• nums = [4, 3, 2, 7, 8, 2, 3, 1]：缺少 5 和 6，输出 [5, 6]。

这些用例之所以重要，是因为它们专门覆盖了“重复元素”“最大最小值”“全出现”和“全缺失”这些极端场景。尤其是 [3,3,3] 这种，三个位置全是同一个数字，很容易暴露出循环里索引计算的错误。我在面试别人时，也特别喜欢拿这些用例去试探候选人是否真的理解原地标记，而不是背诵代码。

4.5 一个容易被忽略的细节：返回结果的顺序

注意第二遍扫描时，你是按索引从小到大的顺序判断的，所以得到的缺失数字天然就是升序的。这点虽然简单，但如果你中途用了集合或者哈希表，最后忘了排序，结果就不是题目期望的顺序了。这也是为什么我建议这道题用数组自身做标记的另一层原因：它连结果顺序都帮你保证好了。

5. 一个技巧带飞一片题：同类问题迁移指南

当你把“值域和索引一一映射、用原数组做标记”这个思维练熟之后，会发现一大批题目其实可以归为一类。

5.1 力扣 41：缺失的第一个正数

这个题是 448 的加强版。数组长度 n，元素可能是任意整数（包括负数、0），要求你找缺失的最小正整数。难点在于值域不再限制在 [1, n]，所以你不能直接把所有元素当成索引来标记。常规做法是第一遍先做“预处理”：把所有不在 [1, n] 范围内的数字统一改成 n+1 之类的哨兵值，然后就可以沿用 448 的原地标记思路了。这类题的识别特征就是：元素范围经过处理后能映射成数组索引。

5.2 力扣 442：数组中重复的数据

442 和 448 几乎是一对镜像题。448 找缺失的，442 找重复的。同样是数值范围 [1, n] 和数组长度 n 的配置。你可以用完全相同的标记法：如果某个位置在标记前已经是负数（或者已经超过阈值），说明当前这个数字已经出现过一次，它就是重复的数。你会发现，当你理解了标记法的底层逻辑之后，这类题从头到尾不需要额外空间，代码结构都差不多。

5.3 力扣 287：寻找重复数

287 题的条件是数组长度 n+1，元素范围 [1, n]，根据抽屉原理必然存在一个重复数。有人用快慢指针做，也有人用原地标记做。如果你在面试中遇到这道题，能同时说出两种思路，并解释各自的时间空间复杂度，会让面试官对你刮目相看。这也是“一个技巧带飞一片题”的最佳例证：同一个标记思想，在不同的题目条件下能演化出不同的解法。

5.4 怎么快速判断一道题能不能用“数组当哈希表”

我给你一个简单的识别清单：

• 数组长度是否与数值范围相关？比如长度为 n 的数组，元素是否在 [1, n] 或 [0, n-1] 范围内？
• 题目是否要求找缺失、重复、出现次数这类问题？
• 是否允许修改原数组？

如果前两条满足且允许修改，基本就能用原地标记法。如果前两条满足但题目明确说“不能修改原数组”，那就要换思路，比如快慢指针或者找环理论。

最后说说我个人刷这道题之后的体会。做 448 之前，我遇到数组题目第一反应永远是开一个哈希表或者计数器，几乎不会考虑“数组本身能不能当结构用”这个选项。做完这道题之后，我再看任何“范围已知”的数组题目，都会本能地问一句：能不能把下标当值用？这个思维转变的价值，远超这道题本身。如果你刚开始接触这类题目，我建议你把取负法和偏移法都写一遍，再拿上面 6 组测试用例逐一手动验证，尤其是 [2,2] 和 [3,3,3] 这两个用例，能把大多数隐藏 bug 暴露出来。原地标记这个思路本身不难，难的是真正理解“标记”和“还原”这两个动作之间的平衡——理解了这一点，这一整类题目你就拿下了。