287. 寻找重复数：数组为什么能转化成链表环

LeetCode 287. 寻找重复数 给出一个长度为 n + 1 的数组，其中每个数都在 [1, n] 内，并且只有一个整数重复出现。要求在不修改数组、只使用 O(1) 额外空间的条件下找出重复数。

这道题最难的不是快慢指针本身，而是想到：数组可以被看成一张链表，而重复数就是链表的环入口。第一次遇到时，这个转化很不自然，所以这篇笔记重点记录“为什么”，而不只是背两段指针代码。

• 287. 寻找重复数 ↗ 本文主问题：把数组解释成函数图，在 O(1) 额外空间内寻找重复数。
• 142. 环形链表 II ↗ 真正的链表版本：使用 Floyd 快慢指针寻找链表开始入环的第一个节点。

题目限制在暗示什么

如果只要求返回重复数，最直观的做法是使用哈希集合：遇到已经出现过的数字就返回。但是集合需要 O(n) 空间，不满足题意。

排序后检查相邻元素也很容易，但排序会修改数组；即使先复制一份再排序，复制又需要 O(n) 空间。题目同时禁止这两条常见路线，说明答案必须利用数组值域的特殊性质。

第一步：把数组读成一张“链表”

通常读取数组时，nums[i] 只是下标 i 处保存的数。现在换一种解释：

• 每个下标 i 是一个节点；
• nums[i] 是节点 i 的下一个节点；
• 也就是定义一条边 i -> nums[i]。

因为所有 nums[i] 都在 [1, n] 中，所以每一步跳转都不会越界。每个节点又恰好只有一个“下一个节点”，这和单链表节点只有一个 next 指针完全相同。它更准确的数学名称是函数图。

用示例完整走一遍

对于 nums = [1, 3, 4, 2, 2]，不要先盯着数组元素排列，而要写出下标到数组值的映射：

第 0 步0→1nums[0] = 1

第 1 步1→3nums[1] = 3

第 2 步3→2nums[3] = 2，第一次到达 2

环内2→4→22 → 4 → 2，从此一直循环

因此从 0 出发得到的路径是：

0 → 1 → 3 → 2 → 4
            ↑       ↓
            └───────┘

节点 2 是环入口，也正是重复数。数组中下标 3 和下标 4 都保存了值 2，对应图中两条边 3 -> 2 和 4 -> 2。

第二步：为什么一定会出现环

从节点 0 开始，每次都按 nums[current] 走到下一个节点。可访问的节点总数有限，而路径可以一直走下去，所以迟早会再次访问某个已经到过的节点。一旦节点重复，后面的路线也会完全重复，于是形成环。

也可以从重复数的角度理解。假设重复数是 d，至少存在两个不同下标 a 和 b，满足：

nums[a] = d
nums[b] = d

在图中，这表示节点 a 和节点 b 都指向节点 d。多条路径在 d 汇合，而每个节点之后又只有唯一的走法，所以继续走下去必然落入循环。

为什么特意从下标 0 出发

数组值只在 [1, n] 内，因此没有任何节点会指向 0。节点 0 像一条只负责进入图的起跑线，它自己绝不可能位于环内。这样，从 0 出发的路线一定是“先经过一段非环路径，再进入环”的标准带环链表结构。

第三步：为什么环入口就是重复数

链表进入环时，环入口有两个不同的前驱来源：

1. 一个来自环外路径的最后一个节点；
2. 另一个来自环内绕一圈后的前一个节点。

两个不同节点都指向环入口，就表示数组中两个不同下标保存了同一个值——环入口这个下标值。因此环入口一定是一个重复的整数。题目又保证只有一个整数重复，所以它只能是题目要求返回的重复数。

这就是整道题的桥梁：

数组里同一个值出现多次
        ⇕
图里多条边指向同一个节点
        ⇕
从 0 出发形成的环入口
        ⇕
重复数

Floyd 快慢指针分两阶段找入口

完成建模后，问题就变成经典的“环形链表 II”：不需要真的创建链表节点，只要把链表中的 p = p->next 换成 p = nums[p]。

阶段一：让快慢指针在环内相遇

慢指针每次走一步，快指针每次走两步：

slow = nums[slow];
fast = nums[nums[fast]];

两者进入环后，快指针会不断缩小与慢指针的环上距离，因此一定会在环中某处相遇。注意这个相遇点通常不是环入口，所以此时不能直接返回。

阶段二：从起点和相遇点同速前进

保留一个指针在相遇点，把另一个指针放回节点 0。然后两个指针都改为每次走一步，它们下一次相遇的位置就是环入口。

为什么第二阶段一定停在入口

设从起点到环入口的距离为 μ，环长为 λ，第一次相遇点距离环入口为 x。相遇时，快指针走过的路程是慢指针两倍，因此两者的路程差是若干个完整环：

μ + x = kλ
所以 μ = kλ - x

从相遇点继续走 μ 步，相当于先走完剩余的 λ - x 步到达入口，再绕若干个整环，最终仍停在入口。与此同时，从节点 0 走 μ 步也刚好到达入口，因此两个同速指针会在那里相遇。

C++ 代码

class Solution {
public:
    int findDuplicate(std::vector<int>& nums) {
        int slow = 0;
        int fast = 0;

        // 阶段一：找到环内相遇点
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // 阶段二：找到环入口，也就是重复数
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

这里使用 do ... while，是因为两个指针初始都在 0。必须让它们至少移动一次，再判断是否相遇；如果直接写成条件为 slow != fast 的普通 while，循环会一次也不执行。

用示例跟踪指针

仍以 [1, 3, 4, 2, 2] 为例：

复杂度

• 时间复杂度：O(n)。两个阶段中每个指针移动的总次数都是线性级别。
• 空间复杂度：O(1)。只使用了两个整数指针。
• 是否修改数组：否。算法只读取 nums。

常见错误

1. 把相遇点直接当作答案。第一阶段只证明指针进入了同一个环，相遇点不一定是入口。
2. 忘记数组值和节点下标的双重身份。nums[i] 能作为下一下标，完全依赖值域是 [1, n]；若数组值可能越界，这个建模就不能使用。
3. 使用普通 while 却都初始化为 0。初始状态已经相等，循环不会执行。应使用 do ... while，或先让指针各走一次。
4. 第二阶段仍让 fast 一次走两步。寻找入口时两个指针必须都一次走一步。
5. 把返回值写成 nums[slow]。相遇时的节点下标 slow 本身就是重复数；虽然在某些自环示例中两者碰巧相同，但一般不能多跳一步。

如果实在想不到链表环

还有一种不修改数组且只用 O(1) 空间的方法：在值域 [1, n] 上做二分，每次统计数组中小于等于中点的数有多少个。若数量超过中点左侧能够容纳的不同整数数量，重复数就在左半边，否则在右半边。这种方法时间复杂度是 O(n log n)。

它比快慢指针更容易从鸽巢原理推导出来，但 Floyd 算法能做到 O(n)。面试或刷题时如果没有立即想到函数图，可以先写出二分计数的可行解，再继续观察“数组值能否作为下标”。

最后总结：这道题应该记住什么

不应该只背“重复数题用快慢指针”，而要记住识别信号：

• 数组中的值全部是合法下标；
• 可以从某个位置出发反复执行 i = nums[i]；
• 题目要求常数空间，不能用访问标记；
• 重复、汇合或无限跳转暗示函数图中存在环。

看到这些条件时，可以尝试把“数组元素”重新解释成“下一跳指针”。一旦完成这次视角转换，寻找重复数就不再是一道神奇技巧题，而是熟悉的链表环入口问题。