1. 为什么“排序”是最诱人的思维陷阱1.1 题目本身在暗示什么先看这道题给定一个包含 n1 个整数的数组 nums其中的数字都在 1 到 n 之间包含 1 和 n可知至少存在一个重复的整数。假设只有一个重复的整数找出这个重复的数。题目本身很短条件也很干净n1 个数塞进 1~n 的值域里那必然有重复这是抽屉原理。很多人的第一反应就是排序把数组排好序然后从头扫一遍前后两个元素相等就说明找到了。这个直觉太自然了我当年学算法的时候看到任何查找类问题第一步想的就是排序加遍历。但后来被面试官连环追问了几次才发现排序其实是这个场景里最典型的“过度整理”。简单算一笔账排序的时间复杂度是 O(n log n)题目给的数据范围如果 n 是 10^5那排序不算慢几毫秒就出结果。如果是 10^7 级别排序就开始吃亏了。但更重要的是这道题既然叫“寻找重复数”核心诉求是“找一条信息”不是“让数据变整齐”。为了找一条信息去把整个数组重新摆一遍就像为了找一个丢失的零件把整个车间的货架全重新码了一遍——能找着但费力气。1.2 排序思维的适用边界我不是否定排序本身排序是算法里的基石很多问题确实要靠排序才能高效解决。比如需要有序输出、TopK 问题、按区间分组统计、归并排序式的逆序对计算这些场景排序就是正解。但“寻找重复数”这个场景有个很特殊的地方你只关心“哪个值出现了不止一次”对顺序没有要求。也就是说目标结果对位置完全不敏感。排序在这个过程中提供的“有序性”是多余信息我们真正需要的只是“相邻比较后能发现重复”这一个效果。用生活化一点的方式说你进房间找一个眼镜正确的做法是扫一圈桌面、翻一下枕头边。但排序思维的做法是先把房间里所有东西按大小码得整整齐齐再挨个看哪个东西出现了两次。前者一分钟搞定后者折腾半个小时后你确实也能找到但中间大部分整理工作做了无用功。这道题更隐蔽的陷阱在于排序解法看起来太合理了以至于很多人交了这个答案之后就没再往下想。如果你只是应付笔试里的简单关卡排序可能真的已经够了。但如果想搞清楚算法思维是怎么一层一层升级的这道题就是一个极好的标本。2. 排序解法的真实成本能跑通但暴露了思维盲区2.1 排序解法的完整实现先给出最朴素的排序解法后面所有讨论都从它出发。我这里用 Python 写逻辑本身跟语言无关def findDuplicate(nums): nums.sort() for i in range(1, len(nums)): if nums[i] nums[i - 1]: return nums[i]逐行解释一下先原地排序然后从下标 1 开始往后遍历只要发现当前元素和前一个元素相等就说明找到了重复值直接返回。这个解法没有任何取巧的地方完全依赖“值相等”和“相邻”这两个概念。如果换成 Java 也会很简洁public int findDuplicate(int[] nums) { Arrays.sort(nums); for (int i 1; i nums.length; i) { if (nums[i] nums[i - 1]) return nums[i]; } return -1; }Java 的Arrays.sort()对对象数组用的是归并排序的变体 TimSort对基本类型数组用的是双轴快排时间复杂度都稳定在 O(n log n) 或者更优。这里需要特别注意的一个细节是Arrays.sort()会直接修改原数组这是一个被很多人忽略的副作用。2.2 排序解法的隐藏问题我实际面试过候选人也模拟过面试官排序解法的隐藏问题主要有四个第一修改了原数组。题目没有说不能改但面试官经常会追加限制条件“不能修改数组”。一旦有这个限制排序解法在思路上就完全不能用了因为你排完序以后数组的顺序已经被打乱了。nums.sort()这一行在 Java 和 Python 里都是原地操作排完序原来的相对顺序就没了。如果题目要求保持数组原样你还得nums.copy()先复制一份空间马上变成 O(n)那跟用哈希表有什么区别。第二时间复杂度的瓶颈。O(n log n) 在 n 小的时候无所谓但在 n 达到 10^7 的场景下排序跑一个亿级别的数据光比较和交换的开销就已经是百毫秒级了。而最优解法后面讲到的 Floyd 判圈算法只需要 O(n) 时间差距在数据规模放大后就非常明显。第三排序没有利用题目给的“值域是 1~n”这个关键信息。这个信息是整个题目的灵魂。只要出现了“n1 个数、值域 1~n”这种结构本质上就在告诉你可以往“从值本身推导位置”的方向想而不是简单复用通用的排序逻辑。第四面试追问环节的尴尬。如果你在面试中只给出排序解法面试官大概率会连续追问你能不能做到 O(n)能不能不用额外空间能不能不修改数组这三个问题任何一个排序解法都无法回答。所以排序不是错而是“交卷太早”把后续所有的进攻空间都堵死了。我自己的体会是排序解法在笔试场景下拿分没问题但在面试场景下容易被判定为“懂基础但缺乏优化意识”。所以如果你准备算法面试这道题至少要做到“排序以外再给出两种解法”的程度后面几章我会把更优解法的思路完整拆开讲。3. 从哈希到原地标记把“记录”这件事做得更聪明3.1 哈希表解法最容易想到的无排序方案很多人说不想排序那就开个哈希表挨个往里放放之前先查一下在不在。这也是一种非常自然的思路逻辑比排序更直白维护一个“已见过的集合”每次遇到新元素先查集合如果已经在集合里就说明重复了。def findDuplicate(nums): seen set() for num in nums: if num in seen: return num seen.add(num)这个方案的时间复杂度是 O(n)空间复杂度也是 O(n)多开了一个最多 n1 长度的集合。在绝大多数场景下这个解法比排序更实用因为平均 O(1) 的哈希查找让整体效率更快而且代码更短、不容易写错。但有经验的面试官一定会追问那句话空间能不能降下来哈希表的本质是“借了一本外部账本”把所有出现过的值记在外面。那自然就有人想到另一种思路既然值域正好是 1~n而数组下标也是 0~n我能不能让数组自己给自己记账这就引出了负号标记法。3.2 负号标记法让数组自己记录“谁出现过”核心思想是遍历数组时把值为 i 的那个“坑位”的数置为负数标记为“i 已经被看见过”。如果遍历到一个数的时候发现它对应的坑位已经是负数说明这个数之前出现过。def findDuplicate(nums): for i, num in enumerate(nums): val abs(num) if nums[val] 0: return val nums[val] -nums[val]这里每一步的意思拆开说第一为什么要取绝对值因为数组里的数可能已经被之前的遍历改为负数了但我们关心的是它原来的值也就是val。一旦被改过就必须用绝对值还原。第二为什么用nums[val]而不是nums[i]因为这里利用的是“值 → 下标”的映射。比如出现数字 3我们就去看下标 3 的那个位置有没有被标记过也就是nums[3]是不是负数。如果已经被改成负数了说明数字 3 出现过第二次直接返回 3。这个解法的时间是 O(n)空间是 O(1)不算输入数组本身的话已经完全超越了排序解法的复杂度。但这个解法的代价也很明确它修改了数组内容把原来的数字都改了符号。如果题目不允许修改数组这个方案同样不能用。有一个更隐蔽的坑值得单独说一下遍历过程中如果当前元素已经被改了符号你只是取它的绝对值来做下标查找绝不可以用它直接去查。否则一旦它本身是负数nums[num]的下标就变成了负数直接越界报错。这段代码里我特意用了abs(num)来避免这个坑。顺便补充一个边界场景如果值是 0负号标记法在带符号数上会失效因为 0 没有正负区分。但本题的值域是 1~n不存在 0所以能放心用。3.3 两套“记账”方案的思维差异哈希表和负号标记法的本质都是「记录某个值是否出现过」区别在于记账本放在哪里。哈希表是“借了外部账本”优点是代码直观、逻辑清晰、不污染原数组缺点是空间 O(n)。负号标记法是“让数组自己记账”利用了输入数据本身可以承载额外的“已见”信号空间降到 O(1)。你也可以这么理解哈希表是去前台翻登记簿负号标记法是直接在门牌号上画勾。前者不会破坏住户的房间但需要一本额外的簿子后者连簿子都不用但把门牌涂改了。从思维层级的角度讲负号标记法的进步点在于开始利用题目本身的特殊结构了。你能主动去问“这题有什么条件是可以白嫖的”而不是套用通用数据结构。这种意识正是从“基础执行者”走向“方案设计者”的分水岭。不过这两套方案都还不算这道题真正意义上的“最优解”因为负号标记法的缺陷是改动了原数组。题目如果把限制条件升级为“不修改数组”就得再往上跳一个层级跳到下一章要讲的 Floyd 判圈算法。4. Floyd 判圈算法把数组当链表是这道题最精彩的思维跃迁4.1 为什么数组可以看成链表第一次听说“用链表的办法解数组题”的人多半会觉得有点穿越。但关键在于要观察到这样一个映射关系数组的每个下标 i 对应一个值 nums[i]这个值本身落在 1~n 之间又是数组的下标之一。于是从 i 出发可以走到 nums[i] 这个位置再从 nums[i] 出发走到 nums[nums[i]] 这个位置——这不就是链表里“通过指针找下一个节点”的逻辑吗就算你看的时候有点懵我建议你拿一个具体的例子推演一遍。比如数组[1, 3, 4, 2, 2]从下标 0 出发0 - 1 (nums[0]1) 1 - 3 (nums[1]3) 3 - 2 (nums[3]2) 2 - 4 (nums[2]4) 4 - 2 (nums[4]2) 2 - 4 - 2 - 4 ...看到了吗走到2 - 4 - 2这一步就进入循环了。正因为数组里有一个重复值导致两个不同下标的“下一步”都指向同一个值链表里就必然出现一个环。题目要求的“找重复数”在这个模型里就等价于“找环的入口”。这个对应关系一旦建立整道题的难度就垂直下降了一大截。链表中已经有一套成熟的环检测算法就是 Floyd 判圈算法也叫快慢指针法。它不需要额外空间也不修改原数组正好命中上一章末尾提到的两个限制条件。4.2 快慢指针的核心实现与推导Floyd 判圈算法的核心思想极其简洁。用两个指针慢指针每次走一步快指针每次走两步。如果链表里没有环快指针会先碰到 null如果链表里有环快慢指针最终一定会在环内相遇。放到这道题里因为题目保证有重复所以必然有环快慢指针必会相遇。第一次相遇后让慢指针回到起点快指针保持在相遇位置然后两人都以每次走一步的速度前进。最终当两指针再次相遇时相遇点就是环的入口也就是我们要找的重复数字。对应到数组上代码如下def findDuplicate(nums): slow nums[0] fast nums[nums[0]] while slow ! fast: slow nums[slow] fast nums[nums[fast]] slow 0 while slow ! fast: slow nums[slow] fast nums[fast] return slow这里的初始化相当讲究值得放慢脚步解释一下。slow nums[0]的含义是“慢指针先走一步”也就是从下标 0 走到下标为nums[0]的位置。fast nums[nums[0]]是“快指针先走两步”先走到nums[0]再走到nums[nums[0]]。这样初始化之后进入循环每次慢指针走一步、快指针走两步才能保证“起跑线一致”。有不少人在这道题上抄过网上给的模板但跑不通原因就出在两个指针的初始值上。如果直接把slow 0; fast 0然后进循环那就相当于两个指针都在起点“等着”第一轮判断while slow ! fast直接就成立了循环根本进不去结果自然不对。4.3 第二次相遇为什么能找到入口为什么必须要有第二次相遇为什么第二次相遇后慢指针放在 0 号位置快指针留在原处两个人同速走一步后就会在入口重逢推导也不复杂。假设链表起点到环入口的长度是 L入口到第一次相遇点的长度是 a环的剩余长度是 b。那么环的总长度就是a b。第一次相遇时慢指针走了L a步快指针走了L a n*(ab)步n 是快指针绕环的圈数。由于快指针速度是慢指针的两倍可得2 * (L a) L a n*(a b) L a n*(a b) L n*(a b) - a这个式子说明从起点走到环入口的距离 L等于从相遇点继续往前走n-1*(ab) b步。回到代码第一次相遇之后我们让慢指针回到下标 0快指针留在相遇点。此时慢指针从起点出发走到环入口需要 L 步快指针从相遇点出发走同样步数后正好也到达环入口。因为上一步已经算出两者在路程上是严格对齐的。如果觉得数学公式还是不够直觉可以换个说法快慢指针第一次相遇后他们俩继续同速前进慢指针每走一步都在一步步丈量“从起点到入口”的距离而快指针则在环内同步消耗“在环内多余绕的圈数”。两人最终会在环口碰上——这是 Floyd 判圈原理中已经被无数题验证过的结论你反复跑几道环形链表的题目比如 LeetCode 142就会彻底接受它。4.4 这个解法的思维层级分析到这里我们已经有了三种解法排序 O(n log n)、哈希表 O(n) 空间 O(n)、负号标记 O(n) 空间 O(1) 但修数组。Floyd 判圈则是 O(n) 时间、O(1) 空间、不修改数组四项指标全部拉满。但我觉得这个解法最值得称道的地方还不是复杂度而是它完成了一次“跨域类比”。很多算法题从小到大都是“数据结构的操作”你训练的是栈、队列、树、图各自的套路。但这道题把数组和链表在逻辑上打通了数组的“值”可以当“指针”用数组的下标可以当“节点”用原本线性规整的结构瞬间变成了一张带环的图。这种抽象能力恰恰是算法思维层级中最难的一步。大多数人卡在“排序→哈希→标记”这三步里不是因为不会写代码而是因为脑子里缺少“把数组看成链表”这种跨模型联想。它不是靠刷题量堆出来的更多是靠遇到难题时主动给自己设问这个结构还能被解释成什么当然这种联想能力也不是纯天赋是可以刻意练习的。日常刷题时如果一道题卡住了我建议强迫自己列出一张“可能的等价视角”清单能不能用双指针能不能用映射能不能用位运算能不能用图论试着从一个完全不同的角度看同一个数据结构这就是思维层级跃迁的训练方法。5. 层级差异的提炼从这道题到日常开发5.1 算法思维的四层阶梯把这道题拆完之后我能很清楚地把“寻找重复数”背后涉及的思维层级归纳成四层这比背下某一题的答案有用得多。第一层是“暴力直觉”。上来就排序因为排序是通用工具不用动脑子缺点是很可能没吃到题目的特殊红利。第二层是“用空间换时间”。看到要找重复第一反应是开哈希表时间确实成了 O(n)但空间多了 O(n)相当于花钱买时间。第三层是“复用已有资源”。意识到数组本身可以当记账本用把正负号当作额外信息空间降到了 O(1)代价是修改了原数组。第四层是“换一个数学结构看问题”。把数组看成链表把问题看成找环入口在不改数组、不用额外空间的前提下做到 O(n) 时间、O(1) 空间。层级方案时间复杂度空间复杂度是否修改数组核心思路L1排序后相邻扫描O(n log n)O(1)原地排序是整理后查找L2哈希表记录O(n)O(n)否外部账本L3负号标记O(n)O(1)是数组自带记账位L4Floyd 判圈O(n)O(1)否数组映射成链表这张表我在面试复盘时自己画过很多次每次看都会有新的体会。同一道题四层解法之间没有一条线是遥不可及的但每一层跃迁的背后都对应一种全新的“提问方式”。排序在问“怎么让重复更好看”哈希在问“怎么记住谁来过”标记在问“能不能就地做记号”Floyd 在问“这个结构还能是什么”。如果每次刷题都能这样逼问自己一圈你的算法能力不可能停滞不前。5.2 别矫枉过正哪些场景排序依然是正解但我也得反向提醒一句不要因为这道题鄙视排序。算法讨论最怕非黑即白好像一提到排序就低级。实际上排序在很多场景里依然是不可替代的最优选择。如果你的问题是“找出前 K 个最大元素且输出有序”排序后取前 K 个是最自然且可读性最高的写法。如果数据量大到内存放不下还有外部排序、归并排序的优化空间。如果要求稳定排序去保证相同键值之间的原始顺序排序就是唯一合理的选择。关键是分清题目要的到底是“有序结果”还是“有序性背后带来的某种副产物”。寻找重复数只想要“相邻性发现重复”这一点那我完全可以绕开排序但如果要输出有序列表那就是另一回事。判断清楚这个分界才是真正的工程思维。还有一类场景中的排序解法是被人低估的数据规模小的时候。n 只有十几二十个数排序的常数因子很小代码也短写起来不容易出 bug。面试中如果你先说“这块数据量小排序足够”再补一句“但如果 n 变大了我可以通过哈希表或快慢指针优化”那给人的感觉会好得多因为你展示了工程判断力而不是只会背模板。5.3 一道题背后的同构问题最后分享一个我很看重的经验一道题学透了最好顺便收集它的“变体地图”。“寻找重复数”这个题稍微改一下条件就会变成不同的经典问题。如果把题目改成“1~n 中缺失的那个数”你会发现方案几乎一模一样用负号标记法遍历最后检查哪个位置没被标记或者虽然也可以排序后找跳变点但明显负号标记法更优雅。如果把题目改成“只出现一次的数”那就是 LeetCode 136 题异或解法一句话就够因为a ^ a 0把整个数组异或一遍剩下的就是那个只出现一次的数。如果把题目改成“多数元素”那又会上 Boyer-Moore 投票算法它同样不需要额外空间思想上也是“用一个计数器来抵消不同值”跟负号标记法有异曲同工之妙。你会发现这些题本质上都在问你同一个问题在“值域受限 数组存储”这种结构里除了排序你还能从哪些角度提取信息练习时把这一类问题放在一起对比思考比零散地刷一百道独立题目有用得多。我个人在带人刷题时最看重的一个指标不是“这道题做没做出来”而是“做完之后能提炼出几个可迁移的思维框架”。框架的数量越多下次遇到新题时就越容易触发联想。这就像积累元器件焊接到一定数量后看到一个电路需求脑子里会自动浮现好几套拼装方案。这也是我为什么反复强调“别一上来就排序”的原因。排序不是不好而是在很多场景下它只是一个思维起点真正有价值的是从起点出发往深走的那几步。下次再碰到看上去很眼熟的查找类问题先停两秒问自己一句除了整理数据之外这道题还有没有别的打开方式