题目要求：
给定一个包含 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
网友评论