这一题我想的方法就很不优雅，想用map，每次插入的时候查看是否已经存在这个元素了
但是看了一下题解，用的都是快慢指针的思想
于是搜索了一下：Floyd 判圈算法
Floyd 判圈算法，又称龟兔赛跑算法，它是一个检测链表是否有环的算法。
原理:
-
判定是否有环: 假设 t 和 h 同时从起点 S 出发, t 的步长是一步, h 的步长是两步, 如果有环, 则 t 与 h 一定会在环上一点相遇, 记为 M.
-
环的长度: 如果判定有环, h 不动, t 绕环一圈回到 h, 就是环的长度.
-
环的起点: h 仍不动, t 回到起点 S, 这时候 t 按原路径走到 h 的距离, 是环的整数倍. 这时候 t 和 h 同时以相同步长(只能是一步)前进, 相遇处便是环的起点, 记为 P.
我们对 nums[] 数组建图，每个位置 i 连一条i→nums[i] 的边。由于存在的重复的数字target ，因此 target这个位置一定有起码两条指向它的边，因此整张图一定存在环，且我们要找到的target 就是这个环的入口
class Solution {
public:int findDuplicate(vector<int>& nums) {int slow = 0, fast = 0;do {slow = nums[slow]; //slow每次走一步fast = nums[nums[fast]]; //fast每次走两步} while (slow != fast);slow = 0; //相遇之后将slow置回到起点while (slow != fast) { //再相遇的时候就是环起点时候slow = nums[slow];fast = nums[fast];}return slow; }
};