本文概览：本文讲解寻找重复数：数组长度为 n+1、值都在 1~n 之间，所以每个值都是一个合法下标，可以把数组读成一张"每个位置指向 nums[位置]"的链表；重复值意味着两个下标指向同一节点，于是形成环，问题就变成找环入口。完整推导快慢指针为什么一定相遇、以及为什么相遇后同速走能停在环入口

一、题目

image-20260929093000001

二、题目分析

1. 题目要求

给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，返回这个重复的数。

要求：

  • 不能修改数组 nums（假设数组是只读的）
  • 只能使用额外的 O(1) 空间
  • 时间复杂度小于 O(n²)

示例 1：nums = [1, 3, 4, 2, 2] → 2

示例 2：nums = [3, 1, 3, 4, 2] → 3

2. 怎么想这题？

题目最后那三条要求才是这题真正的难点，它们把常规的路全堵死了：

  • 哈希表：边遍历边把数字塞进集合，重复的那个一撞就能发现。可惜要多花 O(n) 的空间，违反"O(1) 空间"。
  • 排序：排完之后相邻的重复数字挨在一起，扫一遍就找到了。但排序会改动数组，违反"不能修改数组"。
  • 把值当索引、原地打标记：比如访问过 nums[i] 就把 nums[|nums[i]|] 取负，下次撞见负数就知道重复了。这个思路很妙，但它同样是在改数组，还是不行。

问题就卡在这儿了：既不能多花空间，又不能动数组，那还能往哪看？

换个视角。 注意题目给的两个数字条件：数组长度是 n + 1，而每个值都落在 1 ~ n 之间。把这两句话叠起来看会得到一个很巧的事实：数组里的每一个值，都是一个合法的下标。

既然"值"和"下标"能一一对上，那就换个读法：把每个下标 i 看成一个节点，把它指向的值 nums[i] 看成下一条边的终点。整个数组立刻变成了一张图：

1
i  →  nums[i]        （每个节点只有一条出边）

比如 nums = [1, 3, 4, 2, 2]，读出来就是：

1
2
3
4
5
0 → 1        （nums[0] = 1）
1 → 3        （nums[1] = 3）
2 → 4        （nums[2] = 4）
3 → 2        （nums[3] = 2）
4 → 2        （nums[4] = 2）

从 0 出发顺着箭头走：0 → 1 → 3 → 2 → 4 → 2 → 4 → …，走到 2 之后就再也出不来了——这是一个带环的链表。

为什么会这样？因为"有重复值"意味着两个不同的下标指向了同一个值（nums[3] = nums[4] = 2，都指向节点 2），也就是那个节点有两条入边。顺着走进去，就会绕圈。

于是题目就变了个样子：在一个带环的链表里，找到环的入口。 这正是前面《环形链表 II》做过的事——快慢指针。而且这一次有个额外的好消息：环的入口，恰好就是这个重复数字。

3. 需要解决哪几个问题？

问题一：数组怎么就变成链表了？为什么可以这么读？

问题二：凭什么说这张图里一定有环？

问题三（核心）：快指针一次走两步、慢指针一次走一步，为什么两者一定会相遇？

问题四（核心）：相遇之后，为什么把慢指针放回起点、两个指针都改成一次走一步，再走相同步数，就一定停在环入口？

问题五：环入口为什么正好就是那个重复的数字？

三、思路概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int findDuplicate(int[] nums) {
    int slow = nums[0];
    int fast = nums[0];
    // 第一步：快慢指针找相遇点
    do {
        slow = nums[slow];          // 慢指针走一步
        fast = nums[nums[fast]];    // 快指针走两步
    } while (slow != fast);
    // 第二步：一个回到起点，两者同速前进，相遇处就是环入口
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

思路简要说明：

  1. 把数组当链表：下标 i 指向 nums[i]
  2. 找相遇点：慢指针走一步、快指针走两步，直到两者相遇
  3. 找环入口：慢指针回到起点，两指针改为同速前进，再次相遇的位置就是环入口
  4. 环入口即答案：那个入口正好就是重复的数字
  5. 时间复杂度 O(n)，空间 O(1)

四、思路详解

第一步：解决问题一——数组为什么能读成链表？

关键就是题目那两个条件：数组长度 n + 1、值域 1 ~ n。

值域的上限是 n，而数组的有效下标最大也是 n（下标从 0 到 n）。也就是说，nums[i] 算出来的每个值，都能直接当下标用——这正是"节点 → 下一条边"能成立的前提。

于是定义：

  • 节点就是下标 0, 1, 2, …, n，一共 n + 1 个；
  • 节点 i 有一条出边指向节点 nums[i]。

因为每个节点只指向一个地方，这张图看起来就是一条条单向走的路，可以当成链表来走。从 0 出发，一路 0 → nums[0] → nums[nums[0]] → … 就是遍历过程。

这里有个细节值得记一下：没有哪个 nums[i] 会等于 0（值域从 1 开始），所以没有任何边指向节点 0，节点 0 是整张图里唯一"只出不进"的地方，可以把它当作链表的头。

第二步：解决问题二——环一定存在吗？

一定存在，可以从两个角度看出来。

角度一（追着走一定回头）：从节点 0 出发一路走。因为值域是 1 ~ n，走到的节点永远在 1 ~ n 这 n 个下标里，不可能走回 0。那就是说，从 0 之后只能在 n 个节点里打转——按鸽巢原理，走 n + 1 步必然重复经过某个节点，重复的那一刻就意味着踩进了环里。

角度二（数入边，看"重复"从哪来）：整张图有 n + 1 条边（每个下标各贡献一条）。节点 0 的入度是 0，于是剩下的 n 个节点要分摊这 n + 1 条入边。n 个节点分 n + 1 条边，必然至少有一个节点入度 ≥ 2。

入度 ≥ 2 意味着有两个不同的下标 i ≠ j 都指向它，也就是 nums[i] = nums[j]——这正是"值重复"的定义。所以"有环"和"有重复值"其实是同一件事的两面：重复值让某个节点多出一条入边，而多出来的那条边正是环的来路。

第三步：解决问题三（核心）——快慢指针为什么一定会相遇？

先说结论：只要进了环，就一定会相遇。

道理在于"相对速度"。让慢指针每次走 1 步、快指针每次走 2 步：

  • 两个指针一前一后，都在环上跑的时候，快指针每一轮都比慢指针多走 1 步；
  • 也就是说，快指针在环上"离慢指针还有多远"这个距离，每一轮缩小 1；
  • 环的长度是有限的，记作 b。那么最多 b 轮之后，这个距离就会缩到 0——两者踩在同一个节点上，相遇。

换个说法：快指针是慢指针速度的两倍，但它俩的相对速度只有 1，所以相当于"快指针每轮只用追近 1 格"。环就那么大，追是迟早的事。

那两者一定都会进环吗？会的。慢指针一直在往前走，而链表的尾部就是环，走 a 步（a 表示从起点到环入口的距离）之后就进去了；进去之后它就在环里绕，再也不会出去。两者都进了环，上面的追击就必然发生。

这也解释了为什么"没环时不会相遇"：如果没有环，快指针会先走到尽头（越界），根本追不上谁。而这题一定有空环，所以一定相遇。

第四步：解决问题四（核心）——相遇之后，为什么同速走就能停在环入口？

相遇点已经拿到了，但题目要的是环入口。这里需要一小段数学推导，用的还是前面《环形链表 II》那套符号：

  • a：从起点（节点 nums[0]）到环入口的步数；
  • b：环的长度；
  • s：慢指针走到相遇点时，一共走过的步数。

看两者走过的步数。 慢指针每轮 1 步，快指针每轮 2 步，所以到相遇那一刻：

  • 慢指针走了 s 步；
  • 快指针走了 2s 步。

看两者步数之差。 两者从同一个起点出发，最后停在同一个位置，说明它俩的步数差必然是环长的整数倍（差的这部分就是快指针在环里多绕的圈）。

1
2s - s = s        两者步数差

所以：

1
s = n x b        （n 是快指针多绕的圈数，是一个正整数）

这个式子说明了什么？ 它说明慢指针走到相遇点时，走过的步数恰好是环长的整数倍。

那再看"从起点出发走多少步能到环入口"：从起点走 a 步到环入口，再往前走就是在环里绕圈，绕 n 圈（n x b 步）之后还是会回到环入口。所以：

1
从起点走 a + nxb 步  →  一定落在环入口

拼接起来。 慢指针现在已经在相遇点了，它走过的步数是 s = n x b。如果让慢指针再往前走 a 步，总步数就是：

1
nxb + a = a + nxb   →  正好落在环入口

而另一边，随便派一个指针从起点出发走 a 步，也是落在环入口。

两个人，一个从起点走 a 步，一个从相遇点走 a 步，都停在环入口。 这就是第二阶段的全部依据：

  • 把慢指针放回起点（相当于它从 0 步重新开始）；
  • 快指针留在相遇点（它已经攒了 n x b 步）；
  • 两个指针同速往前走（都每次 1 步）；
  • 各走 a 步之后，同时抵达环入口——两者再次相遇的那个位置，就是环入口。

注意第二阶段两指针速度相同，所以不会再出现"套圈"，它们会在第一次重逢时就停下，那个点就是环入口。

第五步：解决问题五——环入口为什么就是重复的数字？

先看环入口 c 有什么特别。从 0 出发的路径走到 c 之后就在环里绕圈，所以 c 会被两次抵达：一次是从链上进来那一步，一次是在环上绕了一圈回来那一步。这两步分别来自两个节点，而且这两个节点一定不一样——要是同一个节点，说明它自己更早就被重复访问了，会排在 c 前面，和"c 是第一个被重复访问的节点"矛盾。

既然有两个不同的节点都指向 c，c 就至少有两条入边；对应到数组上就是：有两个不同的下标，它们的值都等于 c。也就是说，c 这个值一定是重复出现的。

剩下最后一步就顺理成章了。题目保证"只有一个重复的整数"，而环入口对应的值必然是重复值，那它只能是那唯一的一个。所以第二阶段两个指针在环入口重逢时，返回的位置下标，正好就是题目要的答案。

五、完整执行过程

以示例 1，nums = [1, 3, 4, 2, 2]（答案是 2）为例。先把数组读成链表：

1
2
3
0 → 1 → 3 → 2 → 4
            ▲     │
            └─────┘         环:2 → 4 → 2，入口是 2

第一阶段：快慢指针找相遇点

初始 slow = nums[0] = 1，fast = nums[0] = 1：

1
2
3
4
5
6
7
第 1 轮:  slow = nums[1] = 3
         fast = nums[nums[1]] = nums[3] = 2      slow=3, fast=2，不相等

第 2 轮:  slow = nums[3] = 2
         fast = nums[nums[2]] = nums[4] = 2      slow=2, fast=2，相遇！

相遇点 = 节点 2

第二阶段：回起点后同速前进

slow 重置为 nums[0] = 1，fast 留在相遇点（节点 2）：

1
2
3
4
5
6
7
8
9
初始:  slow = 1, fast = 2

第 1 轮:  slow = nums[1] = 3
         fast = nums[2] = 4                     slow=3, fast=4，不相等

第 2 轮:  slow = nums[3] = 2
         fast = nums[4] = 2                     slow=2, fast=2，相遇！

返回 slow = 2 ✓

两阶段各走了 2 步，最后停在节点 2，正好是重复的数字 ✓。

再验一下示例 2，nums = [3, 1, 3, 4, 2]（答案是 3）：

1
2
3
4
5
6
7
8
9
10
11
12
链表:  0 → 3 → 4 → 2 → 3
                       ▲  │
                       └──┘        环:3 → 4 → 2 → 3，入口是 3

第一阶段:  slow=3, fast=3
  第 1 轮: slow = nums[3] = 4;  fast = nums[nums[3]] = nums[4] = 2
  第 2 轮: slow = nums[4] = 2;  fast = nums[nums[2]] = nums[3] = 4
  第 3 轮: slow = nums[2] = 3;  fast = nums[nums[4]] = nums[2] = 3   → 相遇于节点 3

第二阶段:  slow 重置为 nums[0] = 3;  fast = 3 → 已经相等，不进循环

返回 3 ✓

六、代码细节

do-while 为什么不能用 while？

初始时 slow 和 fast 都等于 nums[0]，是相等的。如果写成 while (slow != fast)，条件一进来就不成立，循环一次都不执行，直接跳出去——等于什么都没算。用 do-while 是"先走一轮再判断"，保证至少走一次。

为什么起点取 nums[0] 而不是 0？

节点 0 的入度是 0（没有任何值等于 0），它不在环上，只是个"入口的入口"。直接从 nums[0] 起步，相当于跳过了节点 0；推导里的 a 也跟着定义为"从 nums[0] 到环入口的步数"。第二阶段慢指针重置回同一个 nums[0]，两边参照系一致，结论不受影响。

快指针两步的写法 nums[nums[fast]] 是什么意思？

nums[fast] 是"往前走一步到达的节点"，再套一层 nums[...] 就是"再往前走一步"，两层嵌套正好代表两步。

会不会越界？

不会。所有值都在 1 ~ n 之间，是合法的数组下标，所以 nums[nums[fast]] 里的两层访问都安全，这也是这道题能"当链表走"的底气。

第二阶段为什么两指针要改成同速？

第一阶段是"套圈"（相对速度 1，一圈圈追近），第二阶段是"同步前进"（速度相同，相对速度 0）。同速前进时两个指针保持固定间距，一旦重逢就是第一次重逢，那个点就是环入口。如果第二阶段还让快指针走两步，就会反复越过环入口，反而抓不准位置。

七、复杂度分析

时间复杂度 O(n)：第一阶段快慢指针最多走 O(n) 步（慢指针至多走 a + b，而 a + b ≤ n + 1）；第二阶段走 a 步，a < n。合起来仍是线性。

空间复杂度 O(1)：只有 slow、fast 两个变量，没有用任何额外数组或集合，也没有修改原数组。

八、总结

这道题看着像是"数组找重复"，但真正的解法是把它读成一张图：

数组里的东西 图里对应的东西
下标 i 一个节点
值 nums[i] 从节点 i 出发的一条边，指向节点 nums[i]
有重复值（两个下标指向同一个值） 某个节点有两条入边
重复的那个值 环的入口节点

之所以能这么读，全靠题目那两个条件："长度 n+1"和"值在 1~n 内"，让值恰好都能当合法下标用。这也解释了为什么常规做法全被堵死之后还有出路——限制条件本身就是线索。

整套推导的关键是两段：

  1. 必相遇：两指针都进环后，快指针每轮比慢指针多走 1 步，环长有限，追近迟早归零。
  2. 遇处找入口：相遇时慢指针走过的步数 s 是环长的整数倍（s = n x b）；而从起点走 a + nxb 步必到环入口。于是让一个指针从起点走 a 步、另一个从相遇点走 a 步，两者同时停在环入口——这就是第二阶段"一个回起点、一个留原地、同速前进"的由来。

顺带一提，这题还有一条不冲突的路子：值域二分。因为重复值 x 满足"小于等于 x 的数超过 x 个"，可以在 1 ~ n 的值域上二分，每次数一遍数组统计数量，时间 O(n log n)、空间 O(1)，也不改数组。不过快慢指针把时间压到了 O(n)，而且思路和《环形链表 II》一脉相承，是这题最漂亮的做法。