题目:寻找重复数
用到了**”环形链表”**的思想
对于含有唯一 一个重复元素的数组,使用快慢指针进行遍历,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}