难度: Medium
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2] 输出：2
示例 2：
输入：nums = [3,1,3,4,2] 输出：3
示例 3 :
输入：nums = [3,3,3,3,3] 输出：3
提示：
1 <= n <= 105nums.length == n + 11 <= nums[i] <= nnums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次进阶：
nums 中至少存在一个重复的数字?O(n) 的解决方案吗？运行时间: 40 ms
内存: 0.0 MB
class Solution:
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
tortoise = nums[0]
hare = nums[0]
while True:
tortoise = nums[tortoise]
hare = nums[nums[hare]]
if tortoise == hare:
break
ptr1 = nums[0]
ptr2 = hare
while ptr1 != ptr2:
ptr1 = nums[ptr1]
ptr2 = nums[ptr2]
return ptr1
这个题解利用了Floyd的乌龟和兔子（循环检测）算法，来寻找重复的数。该算法使用两个指针，一个快指针（兔子）和一个慢指针（乌龟），快指针每次移动两步，慢指针每次移动一步。如果存在一个循环，快指针最终会追上慢指针。这一部分用来检测循环，就像检测链表中的环。一旦快慢指针相遇，就确定了循环的存在，然后使用两个新的指针，一个从头开始，另一个从相遇点开始，每次各走一步，当它们相遇时，就是循环的起点，也就是重复的数。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findDuplicate(self, nums):
# 初始化乌龟和兔子指针
tortoise = nums[0]
hare = nums[0]
# 快慢指针检测循环
while True:
tortoise = nums[tortoise]
hare = nums[nums[hare]]
if tortoise == hare:
break
# 找到循环的起点
ptr1 = nums[0]
ptr2 = hare
while ptr1 != ptr2:
ptr1 = nums[ptr1]
ptr2 = nums[ptr2]
return ptr1
尽管数组nums并不是一个标准的链表结构，但数组中的元素可以看作是指向数组中其他位置的指针（即元素值指向数组的索引）。由于题目中存在重复数字，这将导致至少有一个数字被多个索引指向，形成一个环。这样的结构与链表中的环相似，因此可以使用Floyd的乌龟和兔子算法来检测和找到这个环，进而确定重复的数字。
快指针每次移动两步，慢指针每次移动一步的设置是为了确保如果存在环，快指针可以追上慢指针，从而证明环的存在。这种设置增加了检测环的效率，因为快指针移动得更快，可以更早地发现环的存在或确认环不存在，从而减少了算法的总体执行时间。
在Floyd的算法中，如果快慢指针在非环形结构中移动，则它们永远不会相遇；它们只有在存在环的情况下才会相遇。这是因为快指针每次都跳过了一个节点，如果没有环，它会先到达数组的尽头。只有当存在环，快指针才会绕环运动并最终追上慢指针，从而证明循环确实存在。
根据数学证明和Floyd算法的性质，从数组起点到环起点的距离等于从快慢指针相遇点到环起点的距离。因此，当一个指针从数组起点开始，另一个从相遇点开始，它们以相同速度移动时会在环的起点相遇。由于环的形成是由于数字的重复，所以这个相遇点即为重复的数。