关键在于不能修改原数组以及只能用 O(1) 额外空间
这样排序、set、计数等方法都不行
从额外空间的角度，只能原地修改，或者说使用类似于置换环的形式
这是基于元素的数值范围在 1 到 n 之间所考虑到的，因为置换环的形式能让数字去到它应有的位置，进而达到类似于排序的效果
从这个角度，发现我们如果这样去构造这个图（也就是 i 向 a[i] 连边），那么重复元素对应的那个位置，它的入度将大于 2
因此，相当于我们要找到这个环
这可以参考之前快慢指针找环的思路
class Solution {
public:int findDuplicate(vector<int>& nums) {int fa = 0, sl = 0;while (1) {fa = nums[nums[fa]];sl = nums[sl];if (fa == sl) {break;}}fa = 0;while (sl != fa) {sl = nums[sl];fa = nums[fa];}return fa;}
};
当然，如果时间复杂度不限制为线性，那实际上也有另外一个思路，那就是值域二分，利用抽屉原理，二分答案 mid：
- 统计数组里
<= mid的数有多少个 - 如果数量
> mid，说明重复数在[1, mid] - 否则在
[mid+1, n]