题目:寻找重复数

用到了**”环形链表”**的思想

对于含有唯一 一个重复元素的数组,使用快慢指针进行遍历,fast每次两步(nums[nums[fast]]),slow每次一步(nums[slow]),那么之后一定会产生一个环,而入口就是那个重复的元素

之后只需要再指定一个从起点出发的指针,与slow一起再次进行遍历,最终相遇的位置就是重复数字的位置

(关于环形更具体的解释参见“链表 -> Medium”)

 1int findDuplicate(vector<int>& nums)
 2{
 3    int fast = nums[nums[0]], slow = nums[0];
 4    while(fast != slow)
 5    {
 6        fast = nums[nums[fast]];
 7        slow = nums[slow];
 8    }
 9
10    int finder = 0;
11    while(finder != slow)
12    {
13        finder = nums[finder];
14        slow = nums[slow];
15    }
16    return slow;
17}