题目
给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。
请找出数组中任意一个重复的数，但不能修改输入的数组。
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3。
思考题：如果只能使用 O(1) 的额外空间，该怎么做呢？

解法一：哈希表

找出数组中重复的数字
和上面这题做法一样
时间复杂度O(n)，空间复杂度O(n)

class Solution {
public:
    unordered_map<int, int> rec;
    int duplicateInArray(vector<int>& nums) {
        for (auto x: nums) {
            rec[x]++;
        }
        for (auto it: rec) {
            if (it.second > 1) 
                return it.first;
        }
    }
};

解法二：分治+抽屉原理

数组长度为n+1，范围1~n，因此一定有重复的数字
分治就是每次把取值范围的区间[1, n]划分成[1, n/2]和[n/2+1, n]，分别统计两个区间中数字的个数，一定有一个区间数字的个数是大于区间长度的，这样一来每次就可以将区间长度缩小一半，直到区间长度为1
时间复杂度O(nlogn)，空间复杂度O(1)

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