leetcode 287 寻找重复数 类似环形链表

这个题目很狗屎，强行限定条件，范围是1-n，这样0必然不会被元素指向，构建图时必然可以形成一个狗链形图。这样，唯一的环入口入度是2，就可以套用他的快慢指针算法，很无聊。和力扣142题目一样

classSolution{public:intfindDuplicate(vector<int>&nums){intfast=0,slow=0;while(fast==0||fast!=slow){slow=nums[slow];fast=nums[nums[fast]];}intnew_p=0;while(new_p!=slow){new_p=nums[new_p];slow=nums[slow];}returnnew_p;}};

这个题是比较难的一个题，题目要求不允许修改数组，而且常数空间。这里我们就必须用到数组的1到n规定了。

注：此题和剑指offer 03很像，但是剑指offer那个题不交换基本是没法做的，此题有不修改数组的解法。

此题由于只有一个重复元素，可以使用类似链表的做法，此题其实和环形链表2是一样的，将本身数字当做索引就能一直跳转，由于有重复数字，所以一定能找到环，我们要做的就是找到入环点。代码如下：

classSolution{public:intfindDuplicate(vector<int>&nums){intslow=0,fast=0,tmp=0;while(1){slow=nums[slow];fast=nums[nums[fast]];if(slow==fast)break;}while(1){tmp=nums[tmp];slow=nums[slow];if(tmp==slow)returntmp;}return0;}};