给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]

输出: 2

示例 2:

输入: [3,1,3,4,2]

输出: 3

说明：

数组中至少存在一个重复数

不能更改原数组（假设数组是只读的）。

只能使用额外的 O(1) 的空间。

时间复杂度小于 O(n2) 。

数组中只有一个重复的数字，但它可能不止重复出现一次。

错误的解法：使用map，违背了空间复杂度

class Solution {public:    int findDuplicate(vector<int>& nums) {        std::map<int,bool> hashT;        for(auto i:nums)        {            if(hashT[i])            {                return i;            }            hashT[i] = true;        }        return -1;    }};

这都能提交通过，严重怀疑！！

错误的解法：使用sort，修改排序，违背了数组只读原则

class Solution {public:    int findDuplicate(vector<int>& nums) {                std::sort(nums.begin(),nums.end());        for(int i = 0; i< nums.size() - 1 ; i++)        {            if(nums[i] == nums[i+1])            {                return nums[i];            }        }        return -1;           }};

这也能提交通过，严重怀疑！！

正确的解法：使用环的思想，利用快慢指针查找。

数组中存在重复的数字，必然存在环。

简单分析快慢指针思想, p0 和 p1 是指针, nums[p0] 表示取指针对应的元素

注意 nums 数组中的数字都是在 1 到 n 之间的(在数组中进行游走不会越界),

因为有重复数字的出现, 所以这个游走必然是成环的, 环的入口就是重复的元素,

即按照寻找链表环入口的思路来做

class Solution {public:    int findDuplicate(vector<int>& nums) {        int p0 = nums[0];        int p1 = nums[0];        while(true)        {            p0 = nums[p0];            p1 = nums[nums[p1]];            //找到环的起点            if(p0 == p1)             {                break;            }        }        p0 = nums[0];        while(p0 != p1)        {            p0 = nums[p0];            p1 = nums[p1];        }        return p0;    }};

提交代码通过，耗时可以达到题目要求！！

这道题，你有更好的解法吗？