数组n+1个元素, 元素值范围1到n, 其中有一个重复的元素，寻找重复元素。
要求：
1.不能修改原数组。
2.空间复杂度O(1)。
3.时间复杂度小于O(n^2)。
4.数组中有只有一个重复的元素，但可能重复多次。
思考：如果没有哪些要求解题就比较简单了， 方法也多样，例如（方法1）对原数组进行排序，比较当前元素和前一个元素是否相同。（方法2）借助hash表set，遍历元素，如果set中没有就插入，如果从set中找到证明就是重复的元素了。虽然这两种方法都不满足题意，但是在leetcode中能够accept。下面介绍一个满足要求的求解方法（看了Solution才知道）,解法的开头作者也提到，除非之前听说过cycle detection solution，否则也不太可能想到这种解决方法。（我想也是，哈哈）
解法：使用 cycle detection solution， 就是快慢指针的思想，也类似于求链表中形成环的位置。
int findDuplicate(vector<int>& nums) { int p = nums[0]; int q = nums[0]; do { p = nums[p]; // 相当于是慢指针，一次走一步 q = nums[nums[q]]; // 相当于是快指针，一次走两步 } while(p != q); // 直到走到相遇的位置为止 q = nums[0]; // 一个指针q挪到开头，一个指针p停留在当前位置 while (p != q) { // q,p每次都向前走一步，直到相遇，相遇就是重复的元素 p = nums[p]; q = nums[q]; } return p; }
