LeetCode 287 环检测算法 python实现

题目要求：

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例1：

输入: [1,3,4,2,2]
输出: 2

示例2：

输入: [3,1,3,4,2]
输出: 3

要求：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

参考代码：

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        slow = nums[slow]
        fast = nums[nums[fast]]
        while nums[slow] != nums[fast]:
            slow = nums[slow]
            fast = nums[nums[fast]]
        fast = 0
        while nums[slow] != nums[fast]:
            slow = nums[slow]
            fast = nums[fast]
        return nums[fast]

先看一个基本原理：

image.png

快慢指针同时在起点，快指针每次走两步，慢指针每次走一步。
第一步：

image.png
第二步：
image.png

第三步：

image.png
这时候快慢指针相遇了。

把快指针放到开始位置，和慢指针一样，每次走一步。

image.png

走一步：

image.png

走两步：

image.png
再相遇的时候，就是环的入口，即是重复的那个元素。

为什么再次相遇一定是环的入口？

原理：

image.png
把从开始到环起点的位置长度标为Ａ，环的总长标为Ｌ，从环的入口到快指针慢指针相遇的位置长度标为Ｘ，从相遇位置走到环入口的位置的长度标为Ｙ。
所以可以得到：
慢指针从开始到相遇位置走了A　+　X的长度。
快慢指针相遇的时候，慢指针一定没走完环的一圈。因为当慢指针刚到环上的时候，快指针一定已经到环上了，而且它一直在环上出不去了。又因为快指针速度是慢指针的两倍，所以相遇时必然只绕了一圈。
快指针速度是慢指针的两倍，所以从开始到相遇位置一共走了2（A　+　X）的长度
快指针走过的长度还等于2（A　+　X）　+　K　*　L，意思就是说，快指针走过的长度比慢指针多了ｋ乘以环的长度，也就是快指针可能比慢指针多走了几个环。
所以可以得到2（A　+　X） = （A　+　X）　+　K　*　L。
化简得到A　+　X = K　*　L。
所以Ａ = ｋ　*　Ｌ　-　Ｘ。
因为快指针一定在环上走了超过一圈，所以ｋ一定是大于等于1的，那么可以得到Ａ = （ｋ　-　1）　*　Ｌ　+　Ｌ　-　Ｘ。
Ｌ　－　Ｘ就是Ｙ。
所以得到：Ａ = （ｋ　-　1）　*　Ｌ　+　Ｙ。
所以?的长度即为Ｙ的长度，所以两个指针再次相遇的时候一定在环的入口处。

参考视频：
https://www.bilibili.com/video/BV1w54y1d77K?from=search&seid=12572759627295289696