我第一次刷这道题的时候第一反应是“这还不简单拿一个哈希集合把所有出现过的数字丢进去然后从 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 额外布尔数组法换汤不换药有些人会想那我用一个长度为 n1 的布尔数组把出现过的数字对应位置标成 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]当你走到 i2 的时候nums[2] 已经因为前面的数字 3 而被标记成了 -2不对我们来仔细走一遍。如果前面遍历到 3那么 idx2nums[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的位置对应数字 i1 就是缺失的。因为出现过的数字都把对应位置变成负数了没被碰过的位置自然保持初始正数。这种方法的题解在力扣评论区很常见但能一次写对的人其实并不多问题基本都出在绝对值上。用一个具体例子验证一下取负法的过程。nums [4,3,2,7,8,2,3,1]i0取 nums[0]4idx3nums[3]7 变成 -7i1取 nums[1]3idx2nums[2]2 变成 -2i2取 nums[2]-2abs 之后是 2idx1nums[1]3 变成 -3i3取 nums[3]-7abs 之后是 7idx6nums[6]3 变成 -3i4取 nums[4]8idx7nums[7]1 变成 -1i5取 nums[5]2abs 之后是 2idx1nums[1] 已经是 -3不动i6取 nums[6]-3abs 之后是 3idx2nums[2] 已经是 -2不动i7取 nums[7]-1abs 之后是 1idx0nums[0]4 变成 -4。最终数组变成 [-4, -3, -2, -7, -8, -2, -3, -1]第二遍扫描发现索引 4 和索引 50-based对应的 nums[4]-8、nums[5]-2 都是负数不对等一下我们看第二遍扫描是要找正数这个例子最后全是负数那为什么答案还是 [5,6]因为题目给的输入里 5 和 6 确实没出现过它们对应的位置应该保持正数但这里 nums[4] 被数字 8 标记成负数了呀——它标记的是索引 7 啊。我重新检查一下原数组 [4,3,2,7,8,2,3,1]数字 8 对应 idx7所以 nums[7] 变成负数。那么哪些位置没被标记成负数我们看每个数字对应的 idx数字 4 - idx3nums[3] 变负数字 3 - idx2nums[2] 变负数字 2 - idx1nums[1] 变负数字 7 - idx6nums[6] 变负数字 8 - idx7nums[7] 变负数字 2 - idx1已负不动数字 3 - idx2已负不动数字 1 - idx0nums[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被标记一次后变成 3n再被标记一次变成 32n。那(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)没有性能差异。它的差别主要在写法习惯和边界容错上。对比项取负法偏移法标记方式改为负数加上 n读取原始值abs()取模 % n标记判断位置值 0 才标记位置值 n 则未出现重复元素处理已为负数不再操作可以反复加 n但可能溢出面试表达难度思路直观但要反复强调 abs概念稍绕代码却更简洁我个人的经验是面试时优先用取负法讲思路因为它直观面试官一听就懂实际写题时更爱用偏移法因为循环体里少了一个 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]i0 时nums[0]2idx1把 nums[1] 变成 -1i1 时当前位置 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] 测试i0idx1nums[1]2 变成 -2i1idx1nums[1]-2 又变成 2。好嘛一轮下来索引 1 又变回正数了。第二遍扫描时你会以为数字 2 没出现过白白冤枉它。所以打标记前必须判断目标位置是否还是正数只有正数才需要变成负数。4.3 踩坑三偏移法的判断条件写错边界偏移法第二遍扫描时判断条件是nums[i] n还是nums[i] n这里差一个等于号结果完全不同。如果原始数组里某个元素恰好等于 n它在被标记一次之后值会变成 2n但如果它从来没被标记过值就是 n。如果你写成 n那些原始值正好等于 n 且恰好没出现在数组中的位置会被误判成“已出现”导致漏掉这个缺失数字。所以正确的判断是 n只要值小于等于 n就说明这个位置从来没被标记过对应数字缺失。4.4 边界用例复盘小数组里藏着大问题推荐大家写完代码后把这几个用例手动过一遍n1nums [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] 范围内的数字统一改成 n1 之类的哨兵值然后就可以沿用 448 的原地标记思路了。这类题的识别特征就是元素范围经过处理后能映射成数组索引。5.2 力扣 442数组中重复的数据442 和 448 几乎是一对镜像题。448 找缺失的442 找重复的。同样是数值范围 [1, n] 和数组长度 n 的配置。你可以用完全相同的标记法如果某个位置在标记前已经是负数或者已经超过阈值说明当前这个数字已经出现过一次它就是重复的数。你会发现当你理解了标记法的底层逻辑之后这类题从头到尾不需要额外空间代码结构都差不多。5.3 力扣 287寻找重复数287 题的条件是数组长度 n1元素范围 [1, n]根据抽屉原理必然存在一个重复数。有人用快慢指针做也有人用原地标记做。如果你在面试中遇到这道题能同时说出两种思路并解释各自的时间空间复杂度会让面试官对你刮目相看。这也是“一个技巧带飞一片题”的最佳例证同一个标记思想在不同的题目条件下能演化出不同的解法。5.4 怎么快速判断一道题能不能用“数组当哈希表”我给你一个简单的识别清单数组长度是否与数值范围相关比如长度为 n 的数组元素是否在 [1, n] 或 [0, n-1] 范围内题目是否要求找缺失、重复、出现次数这类问题是否允许修改原数组如果前两条满足且允许修改基本就能用原地标记法。如果前两条满足但题目明确说“不能修改原数组”那就要换思路比如快慢指针或者找环理论。最后说说我个人刷这道题之后的体会。做 448 之前我遇到数组题目第一反应永远是开一个哈希表或者计数器几乎不会考虑“数组本身能不能当结构用”这个选项。做完这道题之后我再看任何“范围已知”的数组题目都会本能地问一句能不能把下标当值用这个思维转变的价值远超这道题本身。如果你刚开始接触这类题目我建议你把取负法和偏移法都写一遍再拿上面 6 组测试用例逐一手动验证尤其是 [2,2] 和 [3,3,3] 这两个用例能把大多数隐藏 bug 暴露出来。原地标记这个思路本身不难难的是真正理解“标记”和“还原”这两个动作之间的平衡——理解了这一点这一整类题目你就拿下了。