给定一个长度为n+1的数组nums，数组中所有的数均在1∼n的范围内，其中n≥1。 请找出数组中任意一个重复的数，但不能修改输入的数组。

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

思考题：如果只能使用O(1)的额外空间，该怎么做呢？

方法1

第一个指针 一次走1, 快指针一次走2
易得第一次相遇时 慢指针一定没有走完一圈,
故慢指针的 路程为X+Y
则快指针路径 为 2X+2Y
我们把慢指针回退到b
那么快指针距离B路程为 y 就是说 快指针距离b点路程为y时路程为2x
我们还可以直到2x+y就是b点
第一次相遇的点处为X+Y
我们把快指针放到a点 以1的速度 再次和慢指针相遇即为b点

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int x = 0, y = 0;
        for (; !x || (x ^ y); x = nums[nums[x]], y = nums[y]);
        for (x = 0; x ^ y; x = nums[x], y = nums[y]);
        return x;
    }
};

方法二

分治的思路
将n个数填入n+1的数组 必然有重复
人为设置区间1-20, 若一边区间内落入的个数 大于 区间内整数的个数那个,这个区间内就必定有重复的数字
while是logn 的,for是n
总的时间复杂度为 nlogn

难点在于 二分的边界选定

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while(l < r) {
            int mid = l + r >> 1; // [l, mid] [mid+1, r]
            int s = 0;
            for(auto num : nums) {
                if(num >= l && num <= mid) s ++;
            }
            if(s > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};