刷题的人应该都遇到过这种尴尬看到找到所有数组中消失的数字这道题第一反应是哈希表一把梭结果读到最后一行发现有个硬性条件——不允许使用额外空间时间复杂度还得控制在 O(n)。很多人在这一步就卡住了因为直觉解法全被这一个限制堵死。这道题真正想问的不是你会不会找缺失值而是你敢不敢在原数组上动手脚。先说人话题目给你一个长度为 n 的数组里面每个元素都在 [1, n] 这个区间内但有些数字出现了不止一次导致另一些数字彻底缺席。要求你把这个数组里没出现的数字全部找出来。示例很直观比如 n 7 的数组 [1, 2, 3, 4, 6, 7, 2]5 没出现那就返回 [5]如果数组是 [4, 3, 2, 7, 8, 2, 3, 1]那就返回 [5, 6]。这道题在算法题库里的编号是 448属于那种解法看起来很简单、但每个解法都藏着边界问题的题目。适合正在刷数组类题目的初学者也适合准备机试、面试的人做思维训练——因为它考察的原地哈希思想能直接迁移到好几道姊妹题上。1. 这道题真正要考验的不是找缺失值而是敢不敢动原数组1.1 先理解约束为什么这题不能直接开哈希表如果把不允许额外空间这条去掉这道题就是一道送分题。常规做法是遍历数组把所有出现的数字放进一个 set再从 1 遍历到 n看哪些数字不在 set 里。整个过程时间复杂度 O(n)额外空间 O(n)代码三行就能写完。但题目明确要求空间 O(1)这个限制直接把最直观的解法堵死了。你不可能用 set因为只要用了哈希结构额外空间就上去了。也不能用布尔数组标记本质上一样占空间。于是问题变成了哪来的空间能当哈希表用答案恰恰是数组本身。你手上的输入就是一个长度恰好为 n 的数组而你要找的数字范围是 [1, n]这两者之间有一种天然映射位置下标 0 对应数字 1下标 1 对应数字 2下标 n-1 对应数字 n。如果每个数字都能落到它对应的位置那么谁的位置上空着谁就是消失的数字。这就是这类题的核心考点你能不能从额外建一个哈希表的思维切换到把原数组当作哈希表的思维。所以我说这道题真正考验的不是查找能力而是你敢不敢修改输入数据、能不能想通下标本身就是一张哈希表这层关系。1.2 为什么这道题允许你破坏原数组很多第一次接触这类题的人会纠结一个伦理问题修改原数组是不是作弊会不会导致后续无法使用原数据在真实的工程项目里修改入参是个需要谨慎决定的事调用方可能根本不知道你动了数组里的值。但算法题里的规则是另一回事。如果题目没有明确说不能修改原数组通常就默认可修改。这道题之所以允许是因为它的返回值只有一份缺失数字列表改完数组之后你唯一需要的信息谁还在原位、谁被标记过就留在数组里了后续不需要再用原始顺序。不过这里有个容易忽略的前提如果面试题或者机试系统额外加了一句请勿修改原数组那这道题的解法就完全不同需要另辟蹊径这个我在后面第 6 节单独讲。只讨论 448 这个原题的话原地修改是通关钥匙。从工程伦理的角度看这类题其实是在考验你另一个能力有没有意识到入参是可变的、以及你修改数据后产生的副作用是可控的。这比单纯会写循环重要得多因为很多真实业务里的性能瓶颈就是大家不敢动已有数据结构宁可反复拷贝数据。2. 从额外哈希表到原地哈希的思路演变2.1 数组下标本身就是一份天然映射理解原地哈希关键要转过一个弯哈希表的本质是给出一个键能快速查到这个键是否出现过、位置在哪。平时我们用字典或者 set是因为数据范围很大、很稀疏没法直接用数组下标做映射。但这道题反过来了。它给的数字范围非常精巧——数组长度是 n所有元素也恰好落在 [1, n] 里。这意味着数字本身就能直接换算成下标数字 v 对应的下标是 v - 1。这不是巧合而是出题人故意设计好的。于是你手里其实已经有一张免费的哈希表一个长度为 n 的数组下标 0~n-1 就是键 1~n 的存储位置。你需要做的只是往这些位置上做标记记录某个数字是否出现过。比如数组 [4, 3, 2, 7, 8, 2, 3, 1]n 8。看到数字 4你就知道它对应的位置是下标 3看到数字 7对应位置是下标 6。如果每个位置最终都能标记为被占用那没被标记的位置其对应的数字就是缺失的。这种数组下标隐含键的组合就是原地哈希。它不要求你真的去设计一个哈希函数也不需要处理冲突——因为数字范围和下标一一对应天然无冲突。2.2 两种常见的标记策略符号标记和值交换想通了下标数字-1以后下一个问题是怎么标记。常见的思路有两类一类是用正负号做标记一类是直接把元素换到对应位置上去。负号标记的思路特别直观遍历数组每看到一个数字 v就把下标 v-1 位置上的数字取成负数。这样一轮下来如果某个位置上的数字仍然是正数说明它的下标对应的数字从头到尾没出现过这就是我们要找的消失的数字。置换法的思路则更物理一点遍历数组不断把当前元素放到它该去的位置也就是把数字 v 放到下标 v-1 处。等全部放完每个位置上的值应该是下标加 1。哪个位置对不上哪个位置对应的数字就缺失。这两种策略各有各的脾气。负号法代码短思路好理解但有个小坑因为你随时可能要读取已经被改写成负数的值所有取下标的地方都必须对值取绝对值。置换法不需要处理绝对值问题但要注意交换时避免死循环。我在后面会分别把两个写法的细节掰开。2.3 为什么标记法是正确且不破坏未来信息的可能有人会问我遍历的时候要读数组里的元素这些元素被我改了符号之后后面再用会不会读错这个问题问得很关键。答案是不会错前提是所有的读取都先用绝对值还原。这个设计的高明之处在于每个元素原本的值是 1~n 之间的正整数它的正负号是我们额外加上去的标记位。无论数组里存的是 2 还是 -2取绝对值之后都能恢复出原始数字 2。这样我们就把原值和标记塞进了同一个整数空间绝对值代表原始数据符号代表这个数字是否出现过。加负号表示我来过保留正则说明没人提起过我。举个实际例子数组 [2, 2, 1]n 3。看下标 0值是 2于是把下标 1 的值 2 改成 -2看下标 1值是 -2取绝对值得到 2再次把下标 1 的值改成负数但发现它已经是负的了说明数字 2 出现过两次看下标 2值是 1把下标 0 的值 2 改成 -2。一轮结束数组变成 [-2, -2, 1]下标 2 对应数字 3还是正数所以缺失的数字是 3。整个过程里负数符号只用于标记绝对值永远保留了原始数字这就是它不会破坏未来信息的原因。3. 负号标记法的代码实现与细节陷阱3.1 核心代码Python 和 C 两种写法先把负号标记法的标准实现放上来这个是我在实际刷题和面试里最常用的版本代码短、不容易写错。Python 版本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]C 版本class Solution { public: vectorint findDisappearedNumbers(vectorint nums) { int n nums.size(); for (int i 0; i n; i) { int idx abs(nums[i]) - 1; if (nums[idx] 0) { nums[idx] -nums[idx]; } } vectorint result; for (int i 0; i n; i) { if (nums[i] 0) result.push_back(i 1); } return result; } };整个算法分两步第一步是标记阶段遍历数组把见过的数字对应的位置取负第二步是收集阶段再遍历一次正数位置对应的下标加一就是要找的答案。标记阶段为什么加一个if nums[idx] 0的判断因为如果这个位置已经被前面的重复数字标记过了再取负不会改变结果反而可能让负数变回正数那就破坏了标记。加判断保证标记只做一次且只做从正变负这一个方向的修改。3.2 为什么必须对每个访问值做 abs 处理这是新手最容易忽略的细节。当你遍历到数组第 i 个位置时nums[i]可能已经不是原始值了它可能是负数——因为这个位置在之前的某次标记中被改写过。比如数组 [1, 1]n 2。第一步nums[0]是 1对应下标 0于是把nums[0]改成 -1。第二步nums[1]还是 1对应下标 0此时nums[0]已经是 -1不需要再改。假如没有if判断直接执行nums[idx] -nums[idx]那么 -1 会被改成 1等于把标记擦掉了。但更关键的是取下标这一步。假设数组是 [2, 2]第一步值 2 对应下标 1把nums[1]改成 -2。第二步读到nums[1]是 -2如果不取绝对值直接用 -2 当下标去访问你会去访问nums[-3]直接越界报错。所以abs(nums[i]) - 1这个写法不是多此一举而是保证程序能正确读取原始值的唯一方式。凡是会对数组元素做标记的题目这类值可能被污染的隐患几乎都会出现记住一个原则在标记类算法里取下标一律基于绝对还原后的值。3.3 三个容易踩的坑重复标记、原始负数、整数边界第一个坑是重复标记。前面已经提过如果同一数字出现多次第一次标记后位置已经是负数后面再遇到必须先判断是否为正数否则会把标记重新翻转回去。这个坑在示例 [1, 1] 里就会立刻触发所以必须加条件判断。第二个坑是原始负数的误解。有人会问题目说元素范围是 [1, n]所以我假设数组里没有负数但如果实际测试数据里出现了负数或者 0 怎么办这种情况在这个题目里不会出现因为题目明确约束了元素范围。但如果你在做类似的变式题比如找到缺失的第一个正数那道题就必须先把负数、零清理掉否则 abs 方案会完全失效。第三个坑是极端值下的整数边界。如果 n 很大比如接近 2^31而某个位置的数字被取负后理论上它的绝对值仍然是原值不会溢出。但如果你写的是nums[nums[i] - 1] -nums[nums[i] - 1]这种嵌套索引代码的可读性会很差也容易改错。我的建议是先算出idx存到局部变量再操作代码清晰也方便调试。下面用一个典型用例把整个过程跑一遍方便你核对输入: [4, 3, 2, 7, 8, 2, 3, 1] 标记过程: i0, v4, idx3, nums[3]7 - -7 i1, v3, idx2, nums[2]2 - -2 i2, v2, idx1, nums[1]3 - -3 i3, v-7, abs7, idx6, nums[6]3 - -3 i4, v8, idx7, nums[7]1 - -1 i5, v2, abs2, idx1, nums[1]已是负数跳过 i6, v-3, abs3, idx2, nums[2]已是负数跳过 i7, v-1, abs1, idx0, nums[0]4 - -4 最终数组: [-4, -3, -2, -7, 8, 2, -3, -1] 收集阶段: 下标4的值80 - 5缺失; 下标5的值20 - 6缺失 输出: [5, 6]4. 置换法把每个数字送回它该在的格子4.1 while 循环交换的原地桶排序思路如果你不太喜欢正负号标记这种方式还有一条完全不同的路置换法。思路和桶排序很像——既然数字 v 应该放在下标 v-1 的位置那我就直接把 v 和那个位置上的元素交换把 v 送回它该去的地方。算法主体是一个带 while 的循环def findDisappearedNumbers(nums): n len(nums) for i in range(n): while nums[i] ! i 1: target_idx nums[i] - 1 if nums[target_idx] target_idx 1: break nums[i], nums[target_idx] nums[target_idx], nums[i] return [i 1 for i in range(n) if nums[i] ! i 1]整个过程可以理解为对号入座每个座位都想坐对的乘客。我走到下标 0 这个座位发现上面坐的是数字 4那不对座位 0 应该坐数字 1于是把 4 送到下标 3 去。下标 3 原来的主人 7 被换过来我再继续处理 7把 7 送到下标 6。这样反复交换直到当前位置坐对了人才去下一个座位。这样一轮之后数组中每个值基本都落回到它应该在的位置。最后再检查一遍谁的位置上坐的不是自己谁就是消失的数字。4.2 死循环问题交换前必须判断目标位是否正确置换法最大的坑是死循环。来看一个典型场景数组 [2, 2]n 2。i 0时while 判断nums[0]是 2不等于 1于是进入循环。目标位置是下标 1检查nums[1]发现它是 2而这正是下标 1 应该坐的值。如果这时你还交换两个元素完全相同交换之后数组不变while 条件依旧成立于是无限循环。解决方式就是我在代码里写的那行提前判断if nums[target_idx] target_idx 1: break意思是目标位置已经坐了对的人说明当前这个值其实是个重复值——它该坐的位置已经被占了那它属于多余的人不需要再交换了退出 while去处理下一个位置。加了这行之后[2, 2] 的处理过程是i0目标下标 1nums[1]恰好是 2直接 breaki1nums[1]等于 2跳过。最终数组还是 [2, 2]扫描时发现下标 0 的值不是 1于是缺失的数字是 1。这个 break 的判断是置换法的灵魂少了它代码在重复元素面前就会挂掉。很多刷题平台提交报超出时间限制的十有八九就是漏了这行。4.3 两种做法的复杂度对比与适用场景从时间复杂度看负号法是严格的 O(n)——每个元素只处理一次加上最后扫描一次。置换法外层虽然有 while但整体均摊也是 O(n)因为每个元素最多被交换一次到它最终的位置不会出现一个元素被反复交换多次的情况。这点当初困扰了我很久后来想明白了每个交换都把一个值送到了它的目标位一旦到位后面不会再动它所以交换总次数不超过 n。两种写法各有适合的场景。如果你需要保留数组的相对顺序置换法是更好的选择因为交换完成后数组几乎是有序桶状态如果只是要答案负号法更短心智负担更小。从面试视角看负号法实现简单适合快速写出正确代码置换法则更接近排序思维适合引导面试官理解你对号入座的想法。我自己的体会是能熟练写负号法保底理解置换法备用两种都要会。5. 从448到442一道题的亲戚们与面试延伸5.1 同样的标记思路反着用找重复出现的数字如果你把 448 这道题的思路反过来就能直接解它的姊妹题数组中重复的数据。那边的要求是找到 [1, n] 范围内出现两次的所有数字同样要求 O(n) 时间、O(1) 额外空间。解法依然是负号标记但收集答案的条件反过来了。遍历时每看到一个数字 v去检查下标 v-1 位置是否是负数如果已经是负数说明 v 之前至少出现过一次把它加入答案如果还是正数就标记为负数。这个思路的精妙之处在于448 收集的是标记后仍然为正的位置442 收集的是想要标记时发现已经被标记的数字。两者共用同一套核心逻辑——数组下标做哈希正负号做标记只是判断时机不同。一道题吃透等于两道题都拿下了。我建议你在刷题时不要只满足于 AC 一道题。做完 448立刻打开 442把同一套解法反着写一遍看能不能一次写对。能的话你就真正理解了原地哈希而不是背答案。5.2 难度升级缺失的第一个正数为什么更麻烦再往后走一步就是那道上过黑名单的经典题缺失的第一个正数。它给你一个无序数组让你找没有出现的最小正整数。数组长度任意元素可能为负、可能为 0范围完全不限制。难度瞬间上来了因为原地哈希没法直接用了——数字范围和数组下标之间不再有天然的一一对应关系。常规破局思路是先把所有不在 [1, n] 区间内的数废掉用一个统一的大数替换掉然后只对 [1, n] 范围内的值做负号标记最后找第一个仍为正数的位置。它和 448 的思维链路完全一致在数据范围受限时用数组下标做哈希范围不受限时先修剪数据再复用同一个套路。理解了这个递进关系你会发现自己看题的方式变了——不再是一个题一个题地背解法而是看到一个题先问三个问题数据范围是什么能否映射到下标修改原数组是否被允许5.3 这类原地哈希题型的通用识别特征我在刷了上百道数组题之后总结出一个规律只要题目同时出现三个条件基本就可以往原地哈希方向靠。第一数组长度和值域强相关。典型标志是长度为 n值在 [1, n]或者值在 [0, n-1]这种说法。这保证了值能安全地换算成下标。第二题目明确或默认允许修改原数组。第三问的是缺失重复出现次数异常这类存在性问题不需要统计具体频次。这三个特征同时出现时不用犹豫直接考虑用遍历代替哈希表的查询用正负号或交换代替哈希表的插入用第二次遍历代替哈希表的遍历。这套方法论比记住某一题的答案重要得多因为它的适用范围覆盖了十几种看起来完全不同的题。做题就像搭积木底层公式就那几个关键是你能不能识别出这道题其实是换了层皮。原地哈希的皮很多但骨架就一个。5.3 不修改原数组的约束下怎么办如果题目加了一条不得修改原数组负号法和置换法全部失效因为两种方法都依赖修改数组内容来做标记。这种时候常见的折中方案是使用额外空间比如布尔数组或者哈希表换回 O(n) 空间。如果连额外空间也不允许那就要么用鸽巢原理配合部分遍历要么承认这道题在工程上很难在纯 O(1) 空间内解决。实际上 448 这种题的设计目的就是引导你接受入参可以被修改这个前提。如果这个前提被否定它就不是一道原地哈希题了而是一道需要更复杂数学技巧的题目。面试时如果遇到这类变种我建议先问清楚约束条件再决定解法方向不要想当然。6. 一些实测心得与调试经验6.1 本地测试要覆盖的边界用例很多代码提交后报错不是思路错而是边界用例没覆盖到。以 448 为例我建议你在本地至少跑这几组[] - [] [1] - [] [1, 1] - [2] [2, 2] - [1] [1, 2, 3, 4] - [] [4, 3, 2, 7, 8, 2, 3, 1] - [5, 6]空数组要注意长度为 0 就直接返回空列表别掉进 n0 的循环里。单元素数组是最容易写错的——如果nums [1]结果显示没有缺失如果nums [2]违反题设范围但实际测试时最好也测一下。重复元素用例 [1, 1] 和 [2, 2] 专治不判断就取负和死循环两类 bug。把这些用例贴在编辑器里每次写完解法先跑一遍再提交能省下不少罚时。6.2 调试符号标记法时如何快速定位错误如果负号法运行结果不对我通常三步排查。第一步打印标记结束后整个数组逐个位置确认哪些被翻成了负数。第二步对照期望正确情况下缺失数字对应的位置一定保持为正数其余位置应该全是负数。第三步如果发现有某个不应标记的位置被标记了往前回溯看它是被哪个值标记的检查那个值是否因为前序操作而没有正确取绝对值。举个例子如果结果是 [5] 而期望 [5, 6]那说明下标 5 的位置被错误标记了。回溯到标记阶段找到哪个v算出了下标 5看看那个v是不是来自一个已经被改成负数的位置。这种排查路径通常五分钟内能定位到问题。置换法的问题定位就更直观了最终数组里凡是nums[i] ! i 1的位置都有问题。你只需要打印最终数组检查有没有位置的值和它的目标位置成环然后看 break 是否在正确时机触发。多数死循环错误在打印一遍交换过程之后就一目了然了。6.3 我个人在实际刷题中的选择建议先说结论正式面试、机试、限时赛里我默认写负号标记法。理由很实际——它代码量最短不容易在忙碌状态下写错且不需要考虑交换死循环这种隐蔽问题。如果你有充裕时间可以再把置换法实现一遍用来向面试官展示你懂得多种思路。如果刷题刚开始接触这类题我强烈建议两种写法都手写完然后再去做 442 和缺失的第一个正数。不要只抄代码一定要在自己的编辑器里重新打一遍跑到 AC 为止。动手写过一次和看过十遍的熟练度差距非常大尤其是 break 这种细节背答案很难背出感觉。最后分享一个小技巧如果你是写 Python 的收集答案那行用列表推导式会非常漂亮但如果推导式写不习惯改成普通 for 循环和 append 也完全没问题。用你最有把握的写法比追求炫技重要得多。这道题解决之后你可能再见到原地修改数组类题目时心里会多一分底气——套路就那些见过的题多了一眼就能识别出来。