题目
给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。
请找出数组中任意一个重复的数，但不能修改输入的数组。
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3。
思考题：如果只能使用 O(1) 的额外空间，该怎么做呢？
思路
将区间范围 [1,n] 进行二分，遍历数组，计算数组元素位于两个区间的数量，如果元素数量大于区间长度，则代表重复元素在此区间，不停迭代。
一分为二，每边至少有一边数字个数是大于坑的数量，找出来再一分为二，划分
logn次
参考答案
class Solution
{
public:
int duplicateInArray(vector<int> &nums)
{
// 对取值区间进行二分
int l = 1, r = nums.size() - 1;
while (l < r)
{
int mid = l + (r - l) / 2;
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 r;
}
};