LeetCode 287. 寻找重复数：把数组当链表的 Floyd 判圈

寻找重复数（LeetCode 287，Medium）是「约束成就解法」的最佳示范：n+1 个数、范围在 1 到 n（鸽笼原理保证至少一个重复）、数组只读（不能排序不能改）、O(1) 额外空间——哈希表被禁、排序被禁、位运算难凑，常规武器全部失效。而题目留下的约束本身，藏着一把钥匙：所有值都在 1..n 之间，且数组有 n+1 个下标（0..n）——把数组当链表：下标 i 的 next 是 nums[i]。这条「链」从下标 0 出发永不越界、必然进入循环——而重复数就是循环的入口。Floyd 判圈算法直接套用。

映射构造：数组即链表，重复数即环入口

映射的定义：定义函数 f(i) = nums[i]——从下标 i 出发，下一步走到下标 nums[i]。因为所有值 ∈ [1, n]，且下标范围是 [0, n]，每一步都落在合法下标内，这条「链」无限延伸。关键推理：如果有重复值 d（出现在至少两个下标 p 与 q），那么 f(p) = f(q) = d——两个不同的节点指向同一个节点 d，这正是链表「环」的结构：从下标 0 出发的路径最终必然进入一个环（下标有限、路径无限 → 必然循环），而环的入口就是「被多个节点指向」的那个节点——即重复值。为什么从 0 出发必然进环且入口是重复数：下标 0 不会被任何 nums[i] 指到（值域是 1..n 不含 0），所以 0 是「链表的尾外头」——从它出发是一条 ρ 形路径（一条尾巴接一个环），而环的入口节点必然有至少两个来路（尾巴的进入 + 环内的循环）——两个来路 = 两个相同的值 = 重复数。这个构造的优雅在于：题目给的每个约束（值域、只读、空间）都不是刁难，而是这个解法的拼图。

Floyd 判圈：两阶段找环入口

Floyd 判圈（快慢指针）分两阶段。阶段一：判断有环并相遇。慢指针每次走一步（slow = nums[slow]），快指针每次走两步（fast = nums[nums[fast]]）——若链无环，fast 会走到「不存在的节点」（本题不会发生：下标永不越界）；有环则快慢必在环内相遇（快比快每轮追近一步）。阶段二：找环入口。相遇后，慢指针回到起点 0，两指针同速前进——再次相遇的位置就是环入口（数学保证：设头到入口距离 a、入口到相遇点距离 b、环长 c，相遇时快走的路程 = 2×慢走的路程，推导出 a ≡ b (mod c)——两指针分别从头与相遇点同速走 a 步后，一个到入口、另一个绕环 c-b+a ≡ a 也到入口）。代码：

def find_duplicate(nums: list[int]) -> int:
    slow = fast = nums[0]              # 阶段一：判圈并相遇
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow = nums[0]                     # 阶段二：找环入口
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow                        # 环入口 = 重复数

时间 O(n)、空间 O(1)——同时满足只读与空间的全部约束。实现细节：初始值用 nums[0] 而不是 0（do-while 语义——先走再比，否则初始相等直接退出）；相遇点不在入口（一般情况），必须走阶段二。

「约束即提示」：这道题的方法论遗产

这道题的真正教学价值，是它示范了如何把约束转化为解法线索。复盘一下推理链：约束「只读、O(1) 空间」排除了什么（哈希、排序、原地标记）→ 剩下的手段只有「利用数组本身的结构」 → 约束「值域 1..n 且 n+1 个下标」恰好定义了一个函数映射 → 函数迭代必有环 → 环检测的经典算法（Floyd）现成可用 → 环入口即重复数。每一步都是「从约束推出唯一可行解法」的推理，而不是「尝试各种算法碰运气」。这条推理链的可迁移模板：遇到被强约束卡死的题，逐条列出「约束排除了什么」，剩下的交集往往就是解法的形状——本库《缺失的第一个正数》（原地哈希：值域 1..n 的数放在下标 1..n——同样是「值域与下标的对齐」线索）是同款推理的姊妹篇。结论：约束不是题目的障碍，是题目的提示——读约束的深度，决定解题的高度。

双哈希对照：O(n)/O(n) 解法的「什么时候它反而更好」

Boyer-Moore 的 O(1) 空间令人惊艳，但工程上有一个诚实的对照：双哈希（Counter）的 O(n)/O(n) 解法什么时候反而更好。场景一：前提不受保证——真实数据不保证多数元素存在，双哈希直接给出完整的频率分布（哪些多、哪些少、有没有多数——一次全知道），Boyer-Moore 只给一个「待验证的候选」（还需第二遍验证）——需要频率全景的场景，哈希是正解。场景二：数据可一次载入且内存无忧——现代服务器的内存对多数业务数据绰绰有余，O(n) 空间的实际成本可忽略——理论的最优空间在工程上常常不构成决策变量。场景三：需要扩展分析——拿到频率分布后追问「第二多的呢」「出现恰好三次的有多少」——哈希表的分布天然支持这些追问，Boyer-Moore 的单候选完全无法回答。Boyer-Moore 的真正主场于是清晰：流式数据（不能存全量）、内存极限（嵌入式、超大规模）、面试的算法素养考察——三个主场之外，双哈希的可读性与信息完备性完胜。方法论总结：O(1) 空间的解法是「算法之美」的展示，O(n) 空间的解法是「工程之实」的选择——知道两个都存在、并能为当前场景选对，才是完整的解题能力。

Floyd 与 Brent：判圈的另一条路

Floyd 判圈之外还有 Brent 算法——判圈的另一条路，值得对比。Brent 的思路：不维护快慢两指针的持续追赶，而是幂次递增的窗口——第 k 轮固定快指针的位置，慢指针走 2^k 步；若在窗口内追上，环长即步数；然后从「快指针位置」重新出发走环长步定位入口。Brent 的优势：比较次数更少（约为 Floyd 的三分之一）——每次「比较」有成本时（函数 f(i) 的计算很贵——本题的 nums 访问便宜，但在函数式迭代器/密码学函数的场景每次迭代都很贵），Brent 的比较节省是实打实的。两者的共同骨架：都基于「快慢追赶必相遇」的原理、都分「判圈」与「找入口」两阶段、入口定位的第二阶段完全相同（同速前进）。选择建议：面试与教材——Floyd（经典、易讲）；函数迭代昂贵的场景——Brent（比较次数敏感时的工程选择）。多知道一个变体的价值不在变体本身，在于它提示你：同一原理可以有不同「成本结构」的实现——为你的成本结构选实现，是算法工程化的一步。

双哈希对照：什么时候它反而更好

Boyer-Moore 的 O(1) 空间令人惊艳，但工程上有一个诚实的对照：双哈希的 O(n)/O(n) 解法什么时候反而更好。场景一：前提不受保证——真实数据不保证多数元素存在，双哈希直接给出完整的频率分布，Boyer-Moore 只给一个待验证的候选。场景二：数据可一次载入且内存无忧——O(n) 空间的实际成本可忽略。场景三：需要扩展分析——拿到频率分布后追问第二多的呢——哈希表的分布天然支持这些追问，Boyer-Moore 的单候选完全无法回答。Boyer-Moore 的真正主场地于是清晰：流式数据、内存极限、面试的算法素养考察——三个主场之外，双哈希的可读性与信息完备性完胜。方法论总结：O(1) 空间的解法是算法之美的展示，O(n) 空间的解法是工程之实的选择——知道两个都存在、并能为当前场景选对，才是完整的解题能力。

Floyd 的应用扩展：从链表到函数迭代的通用环检测

Floyd 判圈的应用远超链表——它是一个「通用环检测器」，适用于一切确定性迭代函数的场景。数学的形式：给定函数 f 和初始值 x0，迭代 x(i+1) = f(x(i))——由于状态空间有限，序列必然进入循环——Floyd 判圈可以找到循环的起点与长度。本题的「数组即链表」是 f(i) = nums[i] 的特例；Pollard's rho 因数分解算法用它检测伪随机序列的循环（质因数分解的应用）；密码学中的离散对数计算也用 Floyd 的变体。通用环检测的实现要点：状态必须是可比较的（判等）、函数必须是确定性的（同样的输入必得同样的输出——非确定性会破坏快慢追赶的数学基础）、以及状态空间必须有限（无限空间的迭代可能不循环）。三个条件的检查是使用 Floyd 前的必要步骤——不是所有迭代都有环——无环的迭代序列（如严格递增）会让快慢指针永远不会相遇。

约束即提示的三层读题法：字面、约束、隐喻

寻找重复数的推理链可以升华为一套通用的读题方法——三层读题法。第一层：字面——题目说了什么（n+1 个数、范围 1 到 n、只读、O(1) 空间）。第二层：约束——题目排除了什么（只读排除了排序和标记、O(1) 空间排除了哈希表）。第三层：隐喻——约束暗示了什么（值域与下标对齐暗示了数组即映射、只读暗示了不可变的映射——不可变映射的迭代就是函数迭代——函数迭代必然循环——循环检测就是 Floyd）。三层读法的训练方法：每做一道题先只读约束部分列出这个约束排除了什么和暗示了什么——约束的排除法与暗示法的组合是所有被强约束卡死的题的解题路线图。

小结

这篇收成四条：「值域 1..n、下标 0..n」把数组变成函数映射 f(i)=nums[i]，迭代路径必然进环，环入口就是被重复指向的重复数；Floyd 两阶段——快慢指针判圈相遇、然后一头一回合同速找入口，时间 O(n) 空间 O(1) 同时满足只读与空间约束；实现细节：初始值取 nums[0]（do-while 语义）、相遇点≠入口、阶段二不可省；方法论遗产——约束不是障碍是提示，「排除法剩下的交集就是解法的形状」，与本库缺失的第一个正数同款推理。这道题值得定期重做：每次重做，都对「约束」二字有更深的敬畏。

参考资料

• LeetCode 287. Find the Duplicate Number —— 题目与官方题解
• Floyd 判圈算法（Brent 也有一个变体）—— 环检测的经典出处
• 本库前篇：《缺失的第一个正数》《LeetCode 141/142 环形链表系列》—— Floyd 的姊妹应用