刷算法题最怕的就是这种题题干两行半读起来像送分题真动笔写却处处是坑。“Find All Numbers Disappeared in an Array找到所有数组中消失的数字”就是这类题的典型代表。我第一次在力扣上刷到它时第一反应是“拿个哈希表记一下再扫一遍1到n不就行了”结果看到题目要求——O(n)时间和O(1)额外空间——那点小得意当场被按回去。哈希表要占空间排序破坏O(n)限制暴力遍历是O(n²)三条路全被堵死。这道题真正想考的是你能不能把数组本身当成一张哈希表来用。这篇笔记我会把这道题从思路到代码再到坑点完整拆一遍。覆盖负号标记法和置换归位法两种主流解法分析它们为什么能在原地完成以及面试官追问“不能修改原数组怎么办”时该怎么接。适合刚把数组基础过完、准备冲击中等难度题目的朋友也适合想在面试里把这个高频模型讲得清清楚楚的老手。先说明一点文中代码以Python为例但核心逻辑和C、Java写法完全一致只看思路也完全够用。1. 先看懂题面三个关键信息与朴素解法的死路1.1 题目在问什么题目给定一个长度为n的数组数组里的每个元素都在1到n这个范围内。但注意它不是1到n的一个完整排列而是其中一些数字可能出现多次另一些数字因此“被挤掉”了。我们要做的就是找出所有在1到n范围内却不在数组中出现的数字。举个例子输入数组是[4, 3, 2, 7, 8, 2, 3, 1]n等于8数字范围是1到8。数组里2和3各出现了两次所以5和6就没有位置了。期望输出是[5, 6]。这个示例几乎出现在所有官方题解里建议先自己对着它把题意嚼明白不是找重复元素而是找缺失元素而且缺失的可能不止一个。这里有个容易忽略的细节题目并没有说数组有序也没有说每个数字只能出现一次。很多初学者会误以为这是一个“排序后比对”的题实际上排序只是其中一条思路但会被复杂度限制直接毙掉。1.2 为什么常规思路全部碰壁先看哈希表方案。遍历数组把每个数字放进一个集合再遍历1到n检查哪个数字不在集合里。这个方案逻辑完全正确时间复杂度O(n)但额外空间是O(n)不满足要求。如果面试题改成“可以不限制空间”这确实是首选因为它最简单、最不容易写错。再看排序方案。先排序再线性扫描找出缺失时间O(n log n)额外空间O(1)。但问题是题目明确要求O(n)时间排序方案在数据量一大就扛不住了。最后是暴力方案。对1到n里的每个数字都在原数组里线性查找一遍看它在不在。这个方案不需要额外空间但时间是O(n²)而且几乎没有优化空间。三条常规路线全被堵死剩下的方向就很清晰了能不能在O(n)时间里完成遍历同时只靠原数组本身记录信息不申请额外内存这就是原地哈希的核心思想。1.3 关键洞察数组本身就是天然的哈希表哈希表的本质是什么是“键到值的映射”。我们这里要判断“数字x是否出现过”如果有一张表能直接回答“x有没有出现”那它就是我们要的哈希表。现在数组下标天然就是0到n-1而数字范围是1到n恰好构成一一对应的关系。数字x对应的下标是x-1这个映射关系不需要额外存储下标就是哈希函数的计算结果。所以问题变成了如何在遍历过程中把“某个数字出现过”这件事记录在它对应的下标位置上并且不破坏数组原有的可用信息。听起来有点抽象但实现思路非常直观看到数字x就去下标x-1的位置做个标记。标记方式可以是把它取负、把它改成特殊值、或者把它换成正确的位置。这就是下面两种解法的共同出发点。2. 解法一负号标记法一个数组当哈希表用2.1 核心思想用正负号打勾负号标记法的思路可以这样理解数组里每个位置都相当于一张“卡片”卡片上的数字是几就代表这个下标对应的那个数字“曾经来过”。遍历到数字x时我去翻下标x-1的那张卡片把卡片上的数字翻成负数相当于打了一个勾。等全部遍历完哪张卡片还是正数就说明对应的那个数字从头到尾没出现过。为什么用正负号而不是改成0或者改成-1因为改成0或-1会彻底丢失这个位置的原始信息后面再访问到它时无法还原出它原本代表哪个数字。而取负操作是“可还原”的——只要用绝对值就能恢复原来的数值。这一点是整个算法成立的前提也是面试官最爱问的细节。2.2 完整代码与逐行拆解def findDisappearedNumbers(nums): n len(nums) # 第一遍遍历给出现过的数字对应的位置打负号标记 for i in range(n): idx abs(nums[i]) - 1 if nums[idx] 0: nums[idx] -nums[idx] # 第二遍遍历收集仍然为正数的位置下标1就是缺失数字 return [i 1 for i in range(n) if nums[i] 0]第一遍遍历里idx abs(nums[i]) - 1这句是核心。为什么这里要套一层abs因为数组在遍历过程中可能已经被改成了负数。比如数组[1, 1]处理第一个1时下标0的位置被标记为-1处理第二个1时nums[1]取出来的值是1但abs(1)还是1所以idx仍然是0不会出错。真正需要注意的是nums[i]本身已经可能是负数的情况比如某个位置之前被别的数字标记过这时如果不取绝对值idx会变成一个负值或越界值直接报错。if nums[idx] 0这一步是防重复标记。如果目标位置已经小于0说明这个数字之前已经出现过了不需要再操作。当然即使不加这个判断把它再取负一次也不会影响最终结果因为我们要的是“符号是否为负”取负两次等于没取。但加上判断可以使逻辑更清晰也方便后续代码改造。第二遍遍历用列表推导式收尾凡是对应下标位置nums[i]仍然大于0的说明数字i1没有出现过加入结果。2.3 为什么这个标记法不会被“污染”很多人第一次看到负号标记会担心一个问题把某个位置改成负数之后如果这个位置本身对应的数字正好在后面要作为“被访问者”出现怎么办举个例子数组[2, 2]n2。处理第一个2时把下标1的位置标记成-2。这时下标0的值还是2下标1的值变成了-2。处理第二个2时idx abs(-2) - 1 1访问下标1发现它已经是负数跳过。最终结果下标0是正数意味着数字1缺失。整个过程没有任何信息丢失因为下标1原本代表的数字2虽然变成了-2但绝对值仍然是2不影响我们判断“2出现过”。这就是原地哈希和普通哈希表的关键区别普通哈希表用键存状态这里用符号位存状态数值本身通过绝对值保留。用大白话说就是“既要在卡片上打勾又不能让卡片上的字消失”。2.4 复杂度与适用范围时间复杂度O(n)第一遍遍历O(n)第二遍遍历O(n)。额外空间O(1)只用了几个临时变量没有申请任何随n增长的存储结构。这是标准的“满足题目全部约束”的解法。但它有一个隐含前提数组元素必须是正数且范围必须严格在1到n之间。如果数组里有0、负数或者超出范围的值取绝对值后映射到的下标可能越界或者下标对应的位置根本没有意义。原题满足这个前提但如果面试官给出变体必须先做预处理。3. 解法二置换归位法让每个数字回到家3.1 核心思想位置错了就交换另一种思路更符合人的直觉既然每个数字x都该待在下标x-1的位置那我就把所有数字都“塞回”它应该待的位置。遍历一遍碰到位置i上的数字x不等于i1就把x换到它该待的位置上去。重复交换直到每个位置都放着正确的数字。最后再扫一遍哪个位置上的数字不等于下标1那个下标1就是缺失数字。这个方案本质上是“强制归位”。它不破坏任何数值信息只是改变了元素的排列顺序。和负号标记相比它更接近“排序”的直觉但又比排序聪明——每个数字最多被交换一次所以总代价仍然是线性的。3.2 完整代码与循环不变式def findDisappearedNumbers(nums): n len(nums) i 0 while i n: target nums[i] - 1 # 如果当前数字不在它该在的位置且目标位置也不是这个数字就交换 if 1 nums[i] n and nums[i] ! nums[target]: nums[i], nums[target] nums[target], nums[i] else: i 1 return [i 1 for i in range(n) if nums[i] ! i 1]这里的关键是交换条件的第二项nums[i] ! nums[target]。这行代码防的是一个特别隐蔽的死循环。如果目标位置上的数字和当前数字相等比如nums[i]3target位置上的值也是3此时交换毫无意义因为两个位置的数字相同交换完还是原样如果不加判断循环会永远卡在这里。所以当目标位置已经是正确数字时只能让i继续前进。整个while循环维持一个不变式下标小于i的所有位置都已经放上了正确数字。每次交换后当前位置会换上目标位置的数字如果这个数字还不是正确位置就继续交换如果已经是了i才前进。为什么这个循环一定终止因为每次交换都会把一个数字放到它的正确位置而一个位置上最多被放置一次正确数字所以交换总次数不超过n。3.3 两种解法对比不是所有“原地”都一样负号标记法和置换归位法都能满足时间和空间要求但气质完全不同。负号标记法胜在代码短、思路直接适合快速解题置换归位法胜在逻辑更“正统”适合作为延伸题的基础模板。我整理了一张对比表面试前看这张表就够复盘了对比维度负号标记法置换归位法时间复杂度O(n)O(n)额外空间O(1)O(1)对原数组的影响部分元素变成负数符号改变元素顺序改变但数值不变代码长度较短稍长找缺失数字最直观同样直观找重复数字需要额外判断不擅长扩展适配“找第一个缺失正数”需要先处理非正数更自然个人经验是如果面试时间紧张优先写负号标记法它代码量少不容易在边界条件上翻车。如果面试官追问“不修改原数组怎么办”或者“如果数组里有0和负数呢”再切换到置换思路去应对。4. 复杂度辨析、变式题与面试延伸4.1 为什么说O(1)空间是成立的很多初学者会问遍历过程中用了idx、target这些变量难道不算额外空间吗严格来说O(1)额外空间指额外空间不随输入规模n增长。几个整数变量无论n是100还是10万占用的空间都是固定常数所以算O(1)。真正不能使用的是那些容量随n增长的容器比如哈希表、集合、新数组。这一点面试时建议主动提一句能立刻显得你懂复杂度分析的本质而不是只会背结论。原地哈希的本质是“用下标当键用数组本身当值域”省掉了哈希表的存储开销。4.2 变式一找出数组中所有重复的数字这道题的变式非常多最经典的就是“找出所有重复的数字”。同样是1到n的数组有些数字出现两次有些出现一次要求找出所有出现两次的数字。思路和负号标记法几乎一样遍历每个数字访问它对应的下标位置如果那个位置已经是负数说明当前数字之前已经出现过加入结果否则就把那个位置取负。代码只需要在原题基础上加一个收集步骤。def findDuplicates(nums): res [] for x in nums: idx abs(x) - 1 if nums[idx] 0: res.append(abs(x)) else: nums[idx] -nums[idx] return res这个变式完美展示了同一个模板的两面原题收集“正数位置”变式收集“重复数字”。把这两个题目放在一起刷原地哈希的模型会记得很牢。4.3 变式二缺失的第一个正数另一道高频题“缺失的第一个正数”也可以复用置换归位法的思想。区别在于那个题里的数组不一定只含1到n的数字可能包含0、负数、甚至大于n的数字所以首先要对数组做一遍预处理——把所有非正数替换成一个不会干扰判断的值比如n1。之后再用置换归位法把1到n范围内的数字放到正确位置。最后再遍历一次返回第一个nums[i] ! i 1的位置。这道题经常被用来考察“同思路套不同场景”的能力。如果你能用两三句话把两道题的关系讲清楚面试官对算法理解深度的印象会直接上一个台阶。4.4 变式三如果面试官要求“不能修改原数组”这是个比较狠的追问因为一旦不允许修改原数组负号标记法和置换归位法都失效了。此时可以用“鸽巢原理 二分查找”的思路统计1到mid这个范围内有多少个数字真的出现在数组里如果数量小于mid说明缺失的数字在1到mid这一半否则在另一半。每次都线性扫描整个数组统计一遍扫描一次O(n)二分O(log n)总体O(n log n)时间、O(1)空间。这个方案时间比O(n)差但胜在满足了“不修改数组”的硬约束。实际面试中不必现场写出完整代码能清晰说出思路就足够应对大多数追问因为面试官更看重的是你能否灵活调整方案。5. 实战中容易踩的坑与调试心得5.1 高频错误速查表我自己在这道题上踩过的坑、以及帮别人review代码时见过的坑基本都集中在下表里。强烈建议照着这个表自查一遍问题现象根本原因解决方案执行报错list index out of range没有对nums[i]取绝对值负数索引越界统一用abs(nums[i]) - 1计算下标结果中混入重复数字用nums[i]本身而不是下标映射把出现过的数字也收集了记得收集条件是“下标位置为正数”置换法死循环交换前没有判断nums[i] nums[target]条件写成nums[i] ! nums[target]再交换结果为空或明显漏数字映射关系写成nums[i]而不是nums[i]-1下标从0开始数字从1开始牢记value - 1面试官说不能动原数组时卡住只会背解题模板不理解本质准备好二分鸽巢方案作为备选5.2 调试技巧把数组状态画出来这类原地算法题最有效的调试方式不是打印最终结果而是把第一遍遍历过程中数组每一步的状态画出来。我调试时习惯在负号标记的循环里加一行临时输出看到底哪些位置被翻成了负数、哪些还保持正数。比如标准示例[4, 3, 2, 7, 8, 2, 3, 1]每处理一个数字后打印数组你会看到下标0和6对应的数字7和1被翻负的时机以及为什么最后只剩下标4和5是正数。这个过程能极大加深对“打勾”行为的理解。5.3 面试表达从题目到方案的三句话如果面试中遇到这道题我建议按这个顺序表达先说明哈希表可行但空间不满足要求接着指出数字范围和数组下标的天然映射关系再抛出原地标记的方案。这三句话能把“为什么这么想”讲清楚面试官通常会在这一步点头。然后写代码边写边解释abs和防重复判断的作用收尾时主动提一句复杂度。实际上这道题最精华的部分不是代码本身而是“看到值域和下标域重合时要想到能用原地哈希”这个思维模型。类似的题目还有“数组中重复的数据”“缺失的第一个正数”“找到所有数组中消失的数字”甚至可以延伸到一些字符串和链表题目。把这一道题吃透相当于同时复习了五六道中等题的公共解法。我自己在刷题笔记里给这道题标注的是“原地哈希模板题”。每次刷到类似的题都会先回到负号标记法的代码上看一眼确认自己有没有把映射关系写反。这里再分享一个小技巧如果担心value - 1和value搞混可以在注释里直接写下“下标等于数字减一因为下标从0开始”这个小注释能省掉很多在草稿纸上重新推导的时间。另外写负号标记法时我习惯把abs(nums[i])单独提出来赋给一个变量比如cur abs(nums[i])再idx cur - 1。这样代码读起来更顺也避免在长表达式里漏掉绝对值符号。看起来只是风格调整但真的能显著降低出错概率。最后再说一个容易被忽略的点这道题返回的结果天然是有序的因为我们是按下标从小到大收集的。有些同学会在最后画蛇添足地调用一次排序不仅多余还可能把复杂度带到O(n log n)。原地哈希的魅力就在“一趟扫过、直接带走”排序这个词在这道题里完全可以删掉。
