287.md

Find the Duplicate Number

解法一

快慢指针

寻找环

func findDuplicate(nums []int) int { // 这种写法是标准的链表双指针寻找环的写法。
    low,fast := nums[0],nums[nums[0]]// 首先制定固有的速率，low是nums[low]的速度，fast是二倍于它的速度就是 nums[nums[0]]
    for low != fast {
        low = nums[low] // 按照不同的速度（存在倍数关系），如果这两者能相遇，就只有一个原因就是因为存在环。
        fast = nums[nums[fast]]
    }
    // 但是他们相遇的地方不一定是入口处，有可能是环的内部的某个元素，这个元素叫做相遇点。
    low = 0// 然后这一步我门要寻找这个环的入口，将low设置为0就是从头开始走，然后fast在相遇点。这个时候把他们的速度调成一样。
    // 即： low = nums[low] fast = nums[fast] 这样速度就一样了，（都是一次，之前速度不同的时候fast直接两次）
    for low != fast {
        low = nums[low]
        fast = nums[fast]
    }
    return low
}