287. Find the Duplicate Number

这一题有几个要求：
首先不能对数组做任何更改，其次，不能使用超过常数的额外空间，而且复杂度不可以超过n**2，所以哈希表法虽然过了，但是没有用啊没有用。看到了一个很棒的办法，利用周期性做的，反正我是没想起来。
如果数组中有一个重复的数字，至少会保证pos = nums[pos-1]这个公式的结果循环出现，代码如下，

class Solution:
    def findDuplicate(self, nums):
        n = len(nums) - 1
        
        # Get into the cycle.至少立庙包含了大于一的循环
        pos = len(nums) # n+1. pos is 1-indexed        
        for _ in range(n+1):
            pos = nums[pos-1]
            
        # Find cycle length 找到循环的长度
        cyc_len = 1
        checkpoint = pos
        while nums[pos-1] != checkpoint:
            pos = nums[pos-1]
            cyc_len += 1
        
        # Advance pointers to find first entrance to the cycle通过一个快一个慢指针同时跑，因为循环一定会相遇，相遇就是重复了
        slow = fast = len(nums)
        for _ in range(cyc_len):
            fast = nums[fast-1]
        
        while slow != fast:
            slow = nums[slow-1]
            fast = nums[fast-1]
        
        return slow
        ```