力扣第 287 题「寻找重复数」我愿称之为 medium 题里的良心之作。题目一句话就能说清楚给定一个长度为 n1 的数组里面每个数都在 [1, n] 范围内而且恰好有一个数字重复把它找出来。但你真正动手写代码时就会发现问题全在三个附加条件上不能修改数组、只能用 O(1) 的额外空间、时间复杂度要尽量低于 O(n²)。这三个限制直接把“排序”“建哈希表”这些常规套路全部堵死逼着你换一种思路去建模。我自己第一次刷这道题时先用集合轻松 AC然后看了一眼题目的空间限制脸都绿了。后来把快慢指针解法彻底搞懂才意识到这道题的“medium”评级一点不虚——它考的从来不是你会不会用哈希表而是你能不能把一个看似跟链表无关的数组转化成链表去处理。1. 先看懂题目三个限制条件才是真正的考点1.1 题目到底长什么样原题描述非常简洁给你一个整数数组 nums长度为 n1所有元素的取值都在 [1, n] 的闭区间内。数组中恰好有一个整数出现了至少两次请你找出这个重复的整数并且要求不能修改原数组额外空间只能是常数级别。注意这里有个容易被忽略的措辞“恰好有一个数字重复”不代表它只多出现一次。LeetCode 官方英文原题里写的是 only one repeated number ... but it could be repeated more than once翻译过来就是这个数字可能连续出现三次、四次甚至更多次。这个细节直接决定了一部分解法能不能用后面我会专门展开。1.2 逐条拆解限制条件第一个限制不能修改数组。这条直接干掉了排序解法。很多人拿到题第一反应是nums.sort()然后扫一遍找相邻相等的元素逻辑简单、代码三行问题在于排序本身就是就地修改数组和题目的硬性要求冲突。哪怕你先把数组复制一份再排序空间复杂度又超了。第二个限制O(1) 额外空间。这条干掉了哈希表/集合解法。用set在遍历过程中判重是最符合人类直觉的方案时间复杂度能做到 O(n)可一旦数组规模到十万级额外空间也跟着线性增长不符合题目对常数空间的执着要求。第三个限制时间复杂度要说得过去。这条主要是卡掉暴力双层循环。最无脑的做法是两层 for 循环枚举所有数对一旦发现相等就返回正确性毫无疑问但 O(n²) 在 n10^5 的规模下必然超时LeetCode 上直接 TLE属于只能用来理解题意的“基线方案”。1.3 这道题真正考察的能力综合来看287 考察的是三件事对时间复杂度与空间复杂度权衡的敏感度、对“索引即指针”这种抽象能力的理解以及能否从数学上证明自己的解法一定能在常数空间内收敛。尤其是最后的快慢指针方案如果你只背代码不理解原理面试时被追问一句“为什么第二次相遇一定是重复数”就会卡壳。所以这一题非常适合用来检验自己是不是真的理解了 Floyd 判圈算法而不仅仅是会默写模板。2. 由浅入深先把能跑的解法全写一遍2.1 暴力双层循环O(n²) 的可怜基线先用最朴素的方式理解问题。既然要找重复那就把所有数两两比较一遍总有一个位置会撞上。Python 写出来长这样class Solution: def findDuplicate(self, nums: List[int]) - int: n len(nums) for i in range(n): for j in range(i 1, n): if nums[i] nums[j]: return nums[i] return -1空间复杂度 O(1)完全符合要求但时间复杂度是 O(n²)。当 n 10^5 时最坏情况要比较大约 50 亿次在 Python 里跑完基本就是一场漫长的等待。LeetCode 对这种解法直接判超时我实测连本地都要跑好几秒。它的意义只在于帮你确认“问题确实能解”仅此而已。2.2 集合判重正确但违反规则的解法接下来是绝大多数人第一个想到的正经解法class Solution: def findDuplicate(self, nums: List[int]) - int: seen set() for num in nums: if num in seen: return num seen.add(num) return -1思路一句话边走边记第一次遇到已经出现过的数就是答案。时间复杂度 O(n)实测在 LeetCode 上能 AC运行速度还很快。问题在于 set 在最坏情况下要存放接近 n 个元素空间复杂度 O(n)直接违背了题目的“constant extra space”。如果你只在本地做题、不在乎题目限制这个解法当然能用但如果你是为了面试用这套解法会被面试官当场追问能不能把空间压到 O(1)这也是为什么我强烈建议别在集合方案上停太久。2.3 排序法为什么“先排序再找”是个陷阱排序法同样看起来很香class Solution: def findDuplicate(self, nums: List[int]) - int: nums.sort() for i in range(1, len(nums)): if nums[i] nums[i - 1]: return nums[i] return -1排序后重复元素必然相邻扫一遍就能找到。时间复杂度 O(n log n)就地排序的话空间复杂度 O(1)单看这两项指标其实都满足。但它修改了原数组和题目第一条限制正面冲突。面试时你要是真写出这个方案面试官大概率会立刻追问“题目说不能修改数组你为什么要 sort 它”所以这道题的排序解法只能作为思维热身不能作为最终答案。3. 二分答案把“找数”变成“计数”3.1 核心思路鸽巢原理如果你仔细看题目会发现一个特别适合二分的结构数字的取值范围是 [1, n]而数组长度是 n1。根据鸽巢原理n1 个元素塞进 n 个桶里必然有桶至少装了两次。更进一步如果我们选择一个中间值 mid统计整个数组里有多少个数小于等于 mid这个计数本身就携带了重复信息。具体推导是这样的如果数组里 1 到 mid 之间的数字“按理说”最多出现 mid 次因为每个数最多出现一次如果完全没有重复的话但现在统计出来的数量大于 mid说明重复的那个数字一定落在 [1, mid] 区间里如果计数小于等于 mid说明 [1, mid] 区间内是“干净”的重复数在 (mid, n] 区间里。这样一来我们不是在数组上二分而是在数值范围上二分每次扫描一遍数组做计数逐步缩小区间。3.2 代码实现class Solution: def findDuplicate(self, nums: List[int]) - int: left, right 1, len(nums) - 1 while left right: mid (left right) // 2 count 0 for num in nums: if num mid: count 1 if count mid: right mid else: left mid 1 return left拿官方示例 [1,3,4,2,2] 走一遍n4left1right4mid2统计数组里 ≤2 的数有 1、2、2 共三个3 2说明重复数在 [1,2] 区间下一轮 left1right2mid1统计 ≤1 的数只有 1 一个1 不大于 1说明重复数不在 [1,1]left 更新为 2。循环结束返回 2正确。3.3 这个方案的优点和局限二分计数方案的时间复杂度是 O(n log n)空间 O(1)不修改数组完全满足题目全部约束在 LeetCode 上可以稳定 AC而且思路清晰、易于在面试中口头解释——这是它最大的价值。我在面试辅导中经常把它作为“标准解法”推荐给候选人因为即便你不知道快慢指针用二分计数也能证明自己掌握了“复杂度和约束的平衡”。不过它的局限也很明显O(n log n) 比最优的 O(n) 慢了一个量级当数组特别大时会体现出差 题。而且这道题的官方最优解期望你想到 Floyd 判圈所以如果想挑战自己还是得迈过快慢指针这道坎。4. 最优解快慢指针Floyd 判圈4.1 把数组看成链表这是整道题最精彩的一步。我们换个视角把每个索引 i 看成链表里的一个节点然后让nums[i]指向下一个节点的索引。也就是说从节点 i 出发走一步会落到节点nums[i]再走一步落到nums[nums[i]]以此类推。举个例子[1,3,4,2,2] 的“指针关系”是0 → 11 → 33 → 22 → 44 → 2。把这个关系画出来你会得到一条从 0 出发、最终绕进一个环的“链表”。核心观察是数组里每个值都在 [1,n] 之间没有任何一个值等于 0意味着“索引 0”这个节点永远不会被任何节点指向它天然是链表起点不可能藏在环里。而从 0 出发沿着指针走总共只有 n1 个节点可以落脚走多了必然重复所以这个结构里一定存在环。4.2 为什么环的入口就是答案把上面的结构想清楚之后一个问题立刻浮现环的入口节点编号和我们要找的重复数到底是什么关系答案是相等。原因很简单环入口节点 c 一定被两个不同来源指向——一个是链表主干上前一个节点 p另一个是环内最后一个节点 b。这两个来源分别意味着nums[p] c和nums[b] c也就是说 c 这个值在数组里出现了至少两次而题目保证只有一个重复数所以 c 就是答案。拿 [1,3,4,2,2] 验证路径是 0 → 1 → 3 → 2 → 4 → 2环为 2 → 4 → 2入口节点编号是 2恰好数组中重复的数字也是 2。这就解释通了。4.3 完整代码与逐行拆解既然已经变成“找链表中环入口”的问题直接用 Floyd 判圈算法的标准套路class Solution: def findDuplicate(self, nums: List[int]) - int: 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第一步初始化快慢指针。慢指针走一步到nums[0]快指针走两步到nums[nums[0]]。这里之所以敢让快指针走两步是因为数组长度是 n1而nums[0]最大是 nnums[nums[0]]的索引最大是 n永远不会越界。第二步两个指针各自前进慢指针每次走一步快指针每次走两步直到相遇。因为环一定存在且快指针比慢指针快两者必然在环内某个位置碰上这一步就是标准的“龟兔赛跑”。第三步让慢指针从 0 重新出发快指针保持原地不动然后两个指针都改成每次走一步。当它们再次相遇时所在位置就是环入口也就是重复数。这一步是整个算法的精华也是面试最容易追问的地方。4.4 数学解释为什么第二次相遇必然在入口要解释清楚第三步需要一点数学。设从起点 0 到环入口的距离为 D环的长度为 C。第一轮中慢指针走了 S 步快指针走了 2S 步两者在距离环入口 x 步的位置相遇。把慢指针的总路程写成 D aC x快指针写成 D bC x由于快指针路程是慢指针的两倍可以得到 D x 是 C 的整数倍也就是说 D ≡ −x (mod C)。第二轮里慢指针从 0 出发走 D 步会到达环入口快指针从第一轮相遇点出发沿环走 D 步。因为 D 与 −x 同余快指针从“入口后 x 步”的位置再走 D 步恰好也回到入口。两者就在入口处再次相遇。如果你觉得数学绕这里给你一个直觉版本第一轮快指针比慢指针多走的距离是环长的整数倍把慢指针拉回起点、两者步伐一致之后它们之间的距离被“补”成了恰好等于入口到相遇点的弧长于是走 D 步后会在入口碰头。我是靠跑了三次示例才彻底接受这个结论的但一旦接受这道题就再也没有秘密了。5. 边界条件与易错点盘点5.1 索引 0 的特殊地位前面提到因为数组值范围是 [1,n]没有任何值等于 0所以索引 0 永远没有入边。这意味着从 0 出发必然能找到环也意味着“以 0 为起点”这个选择不是随便选的而是算法成立的前提。如果你把起点换成别的索引初始状态可能直接落在环里第一轮相遇逻辑照样成立但第二步从 0 出发的证明就不成立了。所以代码里的slow 0千万别改。5.2 快指针会不会越界我第一次写快慢指针解法的代码时最担心的就是fast nums[nums[fast]]这一步。仔细算一下fast 是索引它的取值范围是 0 到 nnums[fast]的取值范围是 1 到 n因为所有值都在 [1,n] 内而数组长度是 n1所以nums[nums[fast]]的索引最大是 n一定在合法范围内。这个性质是题目保证的不需要额外判空。同理慢指针的nums[slow]也不可能越界。5.3 重复多次 vs 只多一次题目说“恰好一个数字重复”但没说它只出现两次。比如[1,1,1,2]这种数组1 出现了三次其他数字出现零次或一次完全合法。这种情况下集合判重依然能正确返回 1二分计数也依然成立快慢指针同样没问题三种方案本质上都只依赖“存在某个值出现至少两次”这个事实不会因为重复次数多而失效。真正会被这个细节影响的是一些基于“其余数字各出现一次”假设的骚操作所以不要想当然地认为测试数据里每个重复数字都只多出现一次。5.4 返回值是值不是索引这个坑特别隐蔽。找链表环入口时我们找到的是“节点编号”而在这个问题里节点编号恰好等于数组元素的值所以直接return slow就好。但如果你把代码写成return nums[slow]那就是把“节点编号”又当成索引去取了一次值结果完全错误。我自己就犯过这个错误调试了半天才反应过来——这道题里索引和值在数字上相等容易让人混淆。6. 常见问题与实操心得6.1 五种解法对比速查表解法时间复杂度空间复杂度是否修改数组能否 AC适用场景暴力双层循环O(n²)O(1)否超时仅用于理解题意集合判重O(n)O(n)否能无空间限制时首选排序后扫描O(n log n)O(1)是能不符合本题约束二分计数O(n log n)O(1)否能面试稳妥答案快慢指针O(n)O(1)否能最优解推荐掌握这张表我建议存下来面试前十分钟扫一眼能把整个思路线拎清楚。核心结论是如果被问到这道题先给集合方案展示基本思路再提出二分计数展示对复杂度的理解最后上快慢指针展示算法功底整个回答就会非常有层次。6.2 面试时怎么讲这道题我在模拟面试中发现候选人最容易崩的点是快慢指针的“为什么”。很多人能写出代码但被问“为什么第一次相遇后把 slow 重置为 0 再走一步就能找到入口”时只能背答案。我的建议是讲的时候先画链表图把数组下标和值的映射画出来再讲两轮循环各自干什么最后补一句“第一轮相遇证明了 D 与 x 的模 C 关系第二轮利用这个关系让两个指针在入口汇合”。哪怕数学细节讲不透能画出图、能解释“入口节点编号等于重复值”面试官通常也会点头。另外有个小技巧这道题和 LeetCode 141环形链表、142环形链表 II是同一套算法体系。如果你在面试里先被问到 141/142可以直接说“我知道 287 也可以用同样的思想解”会加印象分。6.3 刷题扩展同一个套路还能用在哪儿搞懂 287 之后你可以顺手把同类型的几道题串起来刷268 缺失数字、41 缺失的第一个正数、442 数组中重复的数据、448 找到所有数组中消失的数字。它们的共同点是“数组长度和值域存在一一对应关系”很多解法都依赖“用索引标记元素是否出现”这个思想而且部分题目同样有不能修改数组的限制。刷 287 时打下的“索引即指针”的底子刷这些题会非常顺手。6.4 我踩过的几个实战坑最后分享几个实打实的坑。第一个坑是 Python 里// 2和/ 2混用二分计数的 mid 计算一旦写成/得到浮点数后面的nums[fast]就会因为索引类型报错这个错误特别蠢但特别容易犯。第二个坑是 LeetCode 的解法模板里导入了List如果本地直接复制代码跑记得带上from typing import List否则会报 NameError。第三个坑是快慢指针第一轮循环的终止条件有人喜欢写成while True加内部 break有人喜欢直接while slow ! fast两种写法都行但别把两种混合着写那会在边界情况下无限循环。我个人的体会是这道题值得反复刷三遍。第一遍用集合 AC 找手感第二遍仔细推演二分计数第三遍才动手写快慢指针。每次刷完你对“限制条件倒逼算法选型”这件事的理解都会深一层。力扣刷题玩到后面拼的其实不是背了多少题而是能不能在约束下快速建模——287 就是最好的训练场。
