LC 287寻找重复数Find the Duplicate Number　中等

n+1 个数都在 1..n 范围内，必存在一个重复数，在不修改数组的前提下找出它。

思路 把 i→nums[i] 看成有环链表，快慢指针找相遇点后，头与慢指针同速前进，再次相遇处即环入口（重复数）。时间 O(n)。

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