1.题目

2.思路

栗子如上，我们可以将数组下标和对应num值看做一个映射关系，而且将num值看做下一个数组的下标值，即组成了 0-》1-》3-》2-》3，最后的3其实就是2指回了中间的3，也就又回到了环状链表题——使用双指针。

注意：快慢指针最终相遇的点只能确定是在环中的，而非最终的重复数。即快慢指针只能保证会在环内相遇，但是重复数字应该是环入口的数字。

当fast和last相遇之后，我们设置第三个指针pre2，它从起点开始和slow(在fast和slow相遇处)同步前进，当finder和slow相遇时，就是在环的入口处相遇，也就是重复的那个数字相遇。

3.代码

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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/117136842