LC287　寻找重复数¶

中等通过率 68%python3核心代码模式技巧样例通过牛客 AC位运算数组双指针二分查找Floyd 判圈算法抽屉原理

一句话

把「下标 -> 值」看成链表的指针，重复数就是环的入口。

解题思路¶

这题考什么¶

题面给了两条硬约束：不许修改数组、只用 O(1) 额外空间。这两条一起把常规办法全部封死——排序会改数组，哈希集合是 O(n) 空间，「把值 v 交换到下标 v」的原地标记法同样要改数组。

突破口是把数组重新解释成一张函数图：从下标 i 连一条有向边指向 nums[i]。数组长度是 n + 1，下标取值 0..n；而元素值都落在 [1, n]。于是每个点恰好有一条出边，从 0 出发不停地走 i -> nums[i]，步数无上限而点数有限，必然会重复访问某个点——也就是必然进环。

进一步看环的入口。没有任何一条边指向下标 0，因为所有值都 >= 1，所以 0 一定不在环上，从 0 出发的路径形如希腊字母 rho：一条尾巴接一个环。环的入口是第一个「被两条以上的边指向」的点，而某个点 v 有多条入边，等价于值 v 在数组里出现了多次。题面保证只有一个数重复，所以环入口就是那个重复数。

nums = [1, 3, 4, 2, 2]
0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 -> …
               ^         |
               +---------+     入口 2 即答案

找环入口用 Floyd 判圈（龟兔赛跑）：第一阶段慢指针每次一步、快指针每次两步，两者必在环内相遇；第二阶段把其中一个指针拨回起点 0，两者都改为每次一步，再次相遇的点就是入口。

第二阶段的依据是一段简单的路程账。设起点到入口距离 a，入口到相遇点距离 b，环长 c。相遇时慢指针走了 a + b，快指针走了它的两倍，且快指针多绕了整数圈： 2(a + b) = a + b + kc，得 a = kc - b。也就是说从相遇点再走 a 步，正好补满若干整圈回到入口；而从起点走 a 步也到入口，两者同速必在入口相遇。

数据规模与复杂度¶

1 <= n <= 1e5，数组长度 n + 1，1 <= nums[i] <= n。时间 O(n)：两个阶段各不超过若干倍的 n 步；额外空间 O(1)，只有三个整型变量。「值域上二分，数一遍不超过 mid 的元素个数」也满足两条约束，但那是 O(n log n)；抽屉原理的讲法见二分。

坑在哪¶

必须从下标 0 出发。这是整个解法的地基：值域是 [1, n]，没有边指向 0， 0 因此一定在环外，路径才是 rho 形而不是纯环。从别的下标出发，起点可能落在环内，第二阶段的路程账 a = k*c - b 就不再成立，答案会错。
第一阶段是「先走再比」，不能先比。两个指针初值相同，循环写成 while slow != fast 起手就直接退出，一步都不走。用 while True 里先移动后判等（或者让快慢指针错开初值）才对。
第二阶段两个指针的速度都必须是 1。这是路程账推出来的结论，快指针仍走两步就不会在入口相遇。
只能读不能写。这题反复被拿来考的正是「不改数组」，用排序、用交换标记、把访问过的位置取负，都违反题面。
重复数可能出现很多次而不只是两次（题面样例 [3,3,3,3,3] 就是），算法不受影响：入口仍是那个点，它只是入边更多。
Floyd 判圈的通用形式见链表；区别只在于这里的「指针」是下标，「解引用」是一次数组取值。
严格比对：题面保证只有一个数重复，答案唯一，没有多解。

样例复核¶

nums = [1, 3, 4, 2, 2]，边为 0->1, 1->3, 2->4, 3->2, 4->2。第一阶段（slow 一步、fast 两步，都从 0 起，fast 走的是 nums[nums[fast]]）：

第 1 步  slow = 1，fast = 3
第 2 步  slow = 3，fast = 4
第 3 步  slow = 2，fast = 4
第 4 步  slow = 4，fast = 4   相遇于 4（环上的点，不是答案）

第二阶段：slow 拨回 0，fast 留在 4，两者同速一步：

第 1 步  slow = 1，fast = 2
第 2 步  slow = 3，fast = 4
第 3 步  slow = 2，fast = 2   相遇于 2，即环入口

返回 2，与题面一致。注意相遇点 4 本身不是答案，第二阶段那一轮不能省——省掉就会返回环上任意一点。

参考实现¶

solutions/leetcode/LC287/sol.py
from typing import List, Optional


class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # 把数组看成有向图：下标 i 指向 nums[i]。值域是 [1, n] 而下标含 0，
        # 所以没有边指向 0——从 0 出发的路径必是「一段尾巴 + 一个环」，
        # 环的入口被两条以上的边指着，也就是那个重复的数
        slow = 0
        fast = 0
        # 第一阶段：慢指针一步、快指针两步，两者必在环内相遇。
        # 用 while True 先走后判：两个指针初值相同，先判等会一步都不走就退出
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        # 第二阶段：把慢指针拨回起点，两者**同速一步**再走。
        # 依据是路程账 a = k*c - b（a 为起点到入口、b 为入口到相遇点、c 为环长），
        # 从相遇点再走 a 步正好补满整圈回到入口，与从起点走 a 步同时到达
        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        # 相遇处即环入口，也就是重复出现的那个值。全程只读数组，没有任何写入
        return slow

LC287 寻找重复数¶