【c++Leetcode】287. Find the Duplicate Number

本文主要是介绍【c++Leetcode】287. Find the Duplicate Number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题入口

思想：Floyd's Tortoise and Hare

这个算法除了可以检测是否有环（问题入口），还可以用来检测重复数。当然这还需要一个慢指针才能实现。具体请点击标题跳转到原视频，这里是把内容再梳理一遍。如果有不对的地方请多多指教。

这道题的索引和数组取值范围是相关联的。比如长度为5的数组，元素会在[1,4]这个区间。这就可以将索引视为指针，元素视为地址，画出下面这样的图进而观察到重复数的特点。可以发现，重复数会有两个箭头指向它。

这也就意味着，如果从不同方向的两个起点出发都是可以到达重复数的位置。如果两个起点和重复数位置的距离一样的话，那么两个指针一起从起点处出发必然可以相遇，而相遇的位置正好就是重复数的位置。

起点1就是从索引0处开始。那么起点2该如何找到呢？Floyd's Tortoise and Hare算法就派上了用场。快慢指针同时从索引0处出发，它们第一次相遇的位置就是起点2。

这里作者很贴心地举了一个例子帮助大家理解。如下图，两个指针走了三次后最终在3处相遇。

可以看到0和3都和重复数1相差一步。

找到起点2之后我们可以再让一个慢指针从0处出发，两个慢指针同时出发，相遇的位置即重复数。

class Solution {
public:int findDuplicate(vector<int>& nums) {int fast = 0, slow = 0;while (true){fast = nums[nums[fast]];slow = nums[slow];if(fast == slow)break;}int slow2 = 0;while(true){slow = nums[slow];slow2 = nums[slow2];if (slow == slow2)break;}return slow;}};

至于为什么这个结论能够成立，作者通过代数证明。