某在线题库的448题《找到所有数组中消失的数字》几乎每个刷算法题的人都绕不过去。这题本身难度不高但背后的那个核心思路——把数组下标当成哈希表来用会辐射到后面一大片题目属于典型的小题大作用。今天我把这道题从头到尾拆开聊内容包括基础解法、原地标记法的原理与实现、踩过的坑以及面试中常被追问的变体。适合刚入门准备刷题、正在复习数据结构、或者想系统整理数组技巧的人。先看一眼题面给定一个长度为 n 的数组里面元素都在区间 [1, n] 内部分数字出现一次部分数字出现两次要找出所有没有出现的数字。比如[4,3,2,7,8,2,3,1]答案就是[5,6]。没接触过的人第一反应大概率是开一个 set 收集所有出现过的元素再扫一遍 1 到 n 判断谁不在里面。这样解没问题但面试官只要追问一句“能不能 O(1) 额外空间”麻烦就来了。这篇文章会把这些解法全部过一遍重点讲清楚原地标记法为什么能省空间、标记的时候有哪些坑以及如何把这个套路迁移到别的题上。1. 题目到底在问什么三个隐藏条件决定了解题方向1.1 把题面翻译成人话先把这个题目彻底拆开。输入是一个长度 n 的数组 nums元素值都在 [1, n] 闭区间内。这句话里其实藏了三层信息数组长度和值的取值范围相等因为存在重复所以一定有缺失最重要的是元素的“值”天然能和“下标”一一对应。如果数组是一个完美排列那么 nums[i] i 1或者它的某种排列。现在因为重复和缺失导致顺序乱了。我们要找的是那些取值范围在 1 到 n 之间、但在原数组中一次都没出现过的数字。拿样例来说nums [4,3,2,7,8,2,3,1]长度 n 8。其中 2 和 3 出现两次7、8、4、1 各出现一次5 和 6 完全没出现所以结果是 [5,6]。这里最关键的一个观察是每一个元素的值 v都可以对应到一个唯一的下标 v - 1。只要我能标记出“哪些下标被访问过”那么没被标记的下标加 1就是我要找的消失数字。这个观察不是某个技巧的附属品而是整道题的题眼。1.2 题目给你的信号用值与下标的对应关系解题这道题几乎所有解法的核心都是围绕“值 v → 下标 v - 1”这个映射来展开的。区别只在于三点标记信息记在哪里额外数组还是原数组、用什么方式标记布尔值、负号、还是加 n、以及是否需要额外空间。从第一性原理出发我要解决的其实是一个很朴素的问题给我一组数字让我快速判断 1 到 n 里哪些数字没出现过。最朴素的想法是建立一张“出现记录表”。哈希表解法就是把这表建在外面空间 O(n)原地标记法就是想办法把这表建在数组自身空间 O(1)。这个思路想通之后后面不管是负数标记还是加 n 标记都只是实现细节了。很多人卡在这题不是看不懂代码而是没意识到“数组自身就是一张哈希表”这种可能性。一旦意识到你会觉得这题其实没有想象中那么神秘。1.3 这种题在哪里出现、适合谁刷这道题在题库里的编号是 448难度标记通常算是 Easy。但它实际的价值远高于一个简单题的定位。很多中等难度的数组题比如找出重复数据、找出错误的集合底层都是这套“下标即哈希”的思想。把这个简单题吃透后面见到那些题会轻松很多。我的建议是初学者拿它练哈希表的基本使用准备面试的人拿它练空间优化的思维方式已经工作的人可以拿它复习“原地修改数组”时副作用的管理。同一个题在不同阶段能榨出的价值完全不同。2. 从暴力到哈希集先保证对再追求快2.1 最直接的思路先说完全没有优化的暴力做法。对于每个候选数字从 1 到 n在数组中线性扫描一遍统计它出现的次数。外层 n 个数字内层 n 次扫描总复杂度 O(n^2)。出现次数为 0 的就加入结果。这个解法虽然慢但有一个不可忽视的优点逻辑极其简单几乎不可能写错。面试的时候你可以先把它作为“基线解法”提一句分析一下复杂度然后立刻给出更优方案。这比一上来就默写什么花哨技巧更能体现你思考的层次。我很少见到有人真的提交 O(n^2) 的版本但它作为思考起点非常有用。因为从 O(n^2) 到 O(n) 的优化切入点就是“如何避免每次都遍历整个数组来统计次数”。2.2 用哈希集做记录把查找时间降下来稍微进阶一点就是用哈希集合记录数组中出现过的元素。思路很直接先遍历一遍 nums把所有元素加入 set再遍历 1 到 n判断每个数字在不在 set 里不在就加入结果。def find_disappeared_numbers(nums): seen set(nums) n len(nums) res [] for num in range(1, n 1): if num not in seen: res.append(num) return res这个解法的时间复杂度是 O(n)空间复杂度是 O(n)。哈希查找平均 O(1)所以总体是线性时间。如果你没注意到题目的进阶要求这道题写到这一步已经能提交通过了代码也干净。但问题来了一旦面试官说“能不能不用额外空间”这个解法就到底了。注意他说的“额外空间”通常指不随数据规模增长的辅助空间所以真正想要的是 O(1)。2.3 O(n) 空间和 O(1) 空间的分水岭我刚开始刷题的时候总觉得“能跑就行”。后来慢慢意识到面试官更看重的是你清不清楚每一份空间的用途。哈希集版额外开了一个 set最多存 n 个元素所以空间是 O(n)。在题目允许的情况下它完全可用。但 448 这道题的进阶要求写得很明确不用额外空间时间复杂度 O(n)并且假设返回结果用的数组不算额外空间。也就是说你可以用一个数组装答案但不能用它来做中间标记。这道题逼你只能利用原始数组本身。这个限制实际上是给了你一个信号需要把标记信息编码进原数组里。于是“负数标记”和“加 n 标记”这两种经典做法就顺理成章地出现了。3. 核心解法原地哈希标记法O(1) 空间版3.1 核心思想把数组本身改造成哈希表不用另开集合而是把数组下标当作 key把数组元素的符号当作 value。如果某个位置的数是正数说明这个下标没被访问过如果变成负数说明对应的那个数字在原数组里出现过。为什么能这么做因为数组的元素值在 1 到 n 之间数组下标是 0 到 n - 1。对任意值 v它对应的下标是 v - 1。想知道值 v 是否存在只需要看下标 v - 1 处是否留下了“被访问过”的标记。这就是“把数组本身改造成哈希表”的本质。它不是一个 hack而是利用题目给的信息做的一次合理编码。哈希表本身不就是一个把 key 映射到 value 的结构吗在这里key 是元素值value 是“有没有出现过”的布尔信息存储介质直接复用原数组。3.2 用负数做标记的实现具体做法分两遍遍历。第一遍遍历 nums对每个值 v计算 index abs(v) - 1然后把 nums[index] 改成负数如果它还不是负数。第二遍再遍历一次 nums如果某个下标 i 对应的值还是正数说明 i 1 这个数字没出现过加入结果。def find_disappeared_numbers(nums): for v in nums: idx abs(v) - 1 if nums[idx] 0: nums[idx] -nums[idx] return [i 1 for i in range(len(nums)) if nums[i] 0]这里有两个细节值得停下来细说。第一为什么先取绝对值因为前面的遍历可能已经把某些位置改成了负数数组里的值不再可信。取绝对值之后v 仍然保持在 [1, n] 区间内可以安全映射到下标。第二为什么判断 nums[idx] 0 才翻转因为有重复元素。如果某个位置已经被前面一个相同值标记成了负数后面再来一个相同值如果不加判断直接再取负一次负负得正“标记”就被抹掉了。只有正的才翻转能保证重复数字不会造成误判。3.3 用加 n 做标记的另一种写法除了负数标记还有另一个经典变体遍历时把对应位置的值加上数组长度 n。最后扫描时如果某个位置的值仍然小于等于 n说明这个下标从未被加过 n对应的数字就是消失的。def find_disappeared_numbers(nums): n len(nums) for v in nums: idx (v - 1) % n nums[idx] n return [i 1 for i in range(n) if nums[i] n]加 n 法最大的坑是取模。因为某个位置可能被加了好几次 n值已经超过了 n而其他元素在取下标时要用到这个值所以必须用 (v - 1) % n 把它还原到 [1, n] 区间再映射下标。不取模下标就越界了。加 n 的好处是标记状态单调同一个位置被加多少次值只会越来越大不会出现负数标记法那种“负负得正”的取消标记问题。代价是数值范围会膨胀如果 n 很大且语言是 C要考虑 int 溢出风险。3.4 两种标记方式对比方案标记方式被多次标记时状态遍历时是否要特殊处理主要风险负数标记改为负值若不加判断会反标记需要取绝对值忘加判断导致结果错乱加 n 标记增加 n值持续增大状态单调需要取模还原忘了取模导致下标错误从面试角度两种方案都可以聊。我个人更推荐负数标记版本代码短语义直观正负号天然就是一个布尔值。加 n 版本适合在讨论“如何不丢失原值信息”的场景里拿出来做补充显得你想得比较全面。4. 实操过程与完整实现从伪代码到可运行代码4.1 用一个具体例子完整跑一遍拿样例 [4,3,2,7,8,2,3,1] 手工跑一遍负数标记法。n 8。第一遍遍历v 4idx 3nums[3] 7 0置为 -7数组变成 [4,3,2,-7,8,2,3,1]v 3idx 2nums[2] 2 0置为 -2数组变成 [4,3,-2,-7,8,2,3,1]v 2idx 1nums[1] 3 0置为 -3数组变成 [4,-3,-2,-7,8,2,3,1]v 7idx 6nums[6] 3 0置为 -3数组变成 [4,-3,-2,-7,8,2,-3,1]v 8idx 7nums[7] 1 0置为 -1数组变成 [4,-3,-2,-7,8,2,-3,-1]v 2idx 1nums[1] -3 0不翻转v 3idx 2nums[2] -2 0不翻转v 1idx 0nums[0] 4 0置为 -4数组变成 [-4,-3,-2,-7,8,2,-3,-1]第二遍扫描下标 4 的值是 8仍然是正数说明数字 5 消失下标 5 的值是 2仍然是正数说明数字 6 消失。结果是 [5,6]。这个过程强烈建议拿纸笔自己推一遍。我最初刷这道题的时候光看代码总觉得绕手推完一个用例之后“为什么取 abs”“为什么要判断大于 0 才翻转”全部通了。4.2 各语言实现注意事项Python 版最简洁class Solution: def findDisappearedNumbers(self, nums: List[int]) - List[int]: for num in nums: idx abs(num) - 1 if nums[idx] 0: nums[idx] -nums[idx] return [i 1 for i, num in enumerate(nums) if num 0]几个细节在 return 里用 enumerate 同时拿下标和值比 range(len()) 更自然。函数内直接改 nums 没问题因为题目没限制不能修改原数组。如果你不想影响外部数组可以先 copy 一份再操作但那样空间就是 O(n)不推荐用于这题。C 版本需要注意数组被改负后要取绝对值vector 的索引涉及类型转换遇到 v - 1 时先转成 int。vectorint findDisappearedNumbers(vectorint nums) { for (int num : nums) { int idx abs(num) - 1; if (nums[idx] 0) nums[idx] -nums[idx]; } vectorint res; for (int i 0; i nums.size(); i) { if (nums[i] 0) res.push_back(i 1); } return res; }Java 的思路相同把 abs 换成 Math.abs 即可。核心逻辑在所有语言里完全一致真正要小心的永远是符号和下标边界。4.3 复杂度分析与边界条件验证时间复杂度两次线性遍历第一遍标记第二遍扫描总共 O(n)。空间复杂度除了返回结果数组只用常数额外变量O(1)。边界条件值得手动验证几组没有任何缺失nums [1,2,3]长度为 3。遍历后所有位置都变负返回空列表。全部缺失nums [2,2,2]长度为 3。只有下标 1 被标记其余都是正数返回 [1,3]。长度为 1nums [1]。标记下标 0返回空列表。只有重复没有其他数nums [1,1,2,2]长度为 4。数字 3 和 4 确实缺失返回 [3,4]逻辑也正确。这些边界测试我建议写进本地测试里。刷题的时候多花一分钟跑边界面试时就能避免低级失误。5. 常见问题与排查技巧实录5.1 易错点忘了在开始就取绝对值我第一次写这个解法的时候犯的错很典型不取 abs直接用 num 去算下标。结果遍历到已经被改负的位置时idx 变成负数后续所有映射全乱套。正确做法是每次取 abs(num)。一句话记忆标记过程中数组里的值不再可信它们之后只能被当成符号标记来看待真正要用的数字永远是绝对值。5.2 易错点对负数位置重复做翻转有些初版写法是不加判断无条件翻转for num in nums: nums[abs(num) - 1] -nums[abs(num) - 1]这个写法会出问题。数组里出现两次的数字会让同一个下标被连续取负两次负负得正标记就被无故清除了。正确写法是翻转前判断nums[idx] 0保证每个下标最多被标记一次。5.3 易错点加 n 法忘了取模加 n 法里如果遍历过程中 v 已经被加过 n直接用 v - 1 当下标很可能越界。必须写成(v - 1) % n。这里还有个细节如果 v 本身等于 nv - 1 n - 1 是合法最大下标如果 v 是加 n 之后的值取模之后依然落在 [0, n - 1]所以取模是万无一失的。5.4 面试追问如果数组只读怎么办面试官偶尔会把题目改成“不允许修改原数组但仍然要求 O(1) 空间”。这时候原地标记法不能用了。合理的反应是什么如果元素值域是 1 到 n且数组只读那么严格 O(1) 空间就只能牺牲时间。可以聊多轮二分段统计先统计 1 到 n/2 范围内的数字出现次数如果不足 n/2说明缺失在左半部分递归二分继续查。这样时间变成 O(n log n)。这个方案并不完美但重要的是你体现出对“空间与时间取舍”的理解。面试中说出这条路比硬背一个标准答案好得多。5.5 常见问题速查表症状原因解决方法输出结果中出现负数下标用了被改负的值先取 abs 再计算下标输出结果完全乱掉负数位置被反复翻转加 if nums[idx] 0 判断加 n 法报下标越界v 被加 n 后没取模遍历时用 (v - 1) % n加 n 法结果错误把超过 n 的数误判为存在判断时用 n 而非绝对值5.6 我踩过的坑和习惯我刷这道题时印象最深的一次踩坑是在 C 里用了加 n 法测试用例一大结果出现负数错乱一查是 int 溢出了。负数标记法没有数值膨胀的问题因为它只改变符号不扩大数值范围。所以后来面试手写我基本都用负数标记法既有把握又稳。另一个习惯是写完代码后我会在脑海中跑一个长度为 2、元素为 [1,1] 的用例。长度为 2元素只有 1那缺失的应该是 2。实际执行v 1 标记下标 0第二个 v 1 判断 nums[0] 已为负不翻转扫描时下标 1 仍是正数输出 2。整个过程十几秒能快速验证逻辑没有方向性错误。6. 由这道题延伸出去的解题套路6.1 数组下标哈希法的通用模板把原地标记法抽象成模板其实就是三步找到值 v 与下标 index 的映射函数 f在数组上打一个可识别、可恢复的标记扫描数组根据标记判断哪些下标被访问过。在 448 里f(v) v - 1标记方式是负数或加 n。在“找出数组中重复数据”的问题里f(v) 还是 v - 1但判断逻辑变成遍历时如果发现目标位置已经被标记过说明当前值和之前某个值指向同一个位置那它就是重复数字。所以这个模板可以覆盖“找缺失”“找重复”“找丢失 重复”三类问题。你只需要调整第三步的输出方式。6.2 相关题目快速对照题号描述与 448 的关系448找到所有数组中消失的数字本题基准标记后取正数为缺失268缺失数字只缺一个可以用求和或位运算也可以用标记法442数组中重复的数据同样的标记法反过来找重复645错误的集合缺失 重复标记法一次遍历同时找缺失和重复我刷 448 时顺手把 268、442、645 三个题一起刷了。它们共享同一个底层观察只是输出方向不同。把 448 彻底吃透后面三道题基本能秒解这就是典型的“一道题带出一类题”。6.3 什么时候不能用原地标记法这个套路很漂亮但不是万能。两个关键限制第一元素值域必须能映射到数组下标。如果值可能为负数、零或者数值范围远大于数组长度映射关系就断了。第二标记过程不能破坏后续计算所需的信息。负数或加 n 是可逆标记能从被标记的值还原出原始值所以能继续处理如果标记方式不可逆后面的遍历就全废了。遇到只出现一次的数字、统计字母出现次数这类题目该用位运算就用位运算该用频率数组就用频率数组不要硬套模板。6.4 这类题的时间与空间博弈面试中很多题都会问“能不能优化空间”。优化空间通常意味着一条路修改原数组做标记或者利用位运算或者用数学性质。448 的数学性质就是“值域与长度重合”所以才能原地。如果是只读题就要和面试官讨论清楚限制条件不要轻易承诺 O(1) 空间。我自己的经验是遇到数组相关的哈希题先问自己三个问题值域是什么下标能代表什么修改原数组是否被允许这三个问题想清楚解法范围基本能缩小一大半。这三个问题也是 448 教会我的最核心的东西。这题我刷过不止一次每次重新看都能发现一点新东西。第一次只是背会了负数标记法的代码第二次理解了为什么数组本身能当哈希表第三次开始思考如果数组只读怎么办第四次才敢在别人问起时相对系统地讲清楚整个思维链路。如果你现在也在准备算法面试我的建议是不要满足于提交通过。花十分钟手推一个用例把“为什么取 abs”“为什么判断大于 0 才翻转”能讲给别人听这道题才算真正掌握。后面再见到 268、442、645 这些兄弟题你会有一种“早就见过你”的熟悉感那种感觉比多刷一百道重复题都值。