给定一个长度为 $n+1$ 的数组nums，数组中所有的数均在 $1∼n$的范围内，其中 $n≥1$。

请找出数组中任意一个重复的数，但不能修改输入的数组。

样例

1
2
3

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

返回 2 或 3。

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

解题思路： 抽屉原理

抽屉原理：$n+1$ 个苹果放在 n 个抽屉里，那么至少有一个抽屉中会放两个苹果。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        int l = 1,r=n;
        while(l<r) {
            int s = 0;
            int mid = l+r >>1;
            for(int u: nums)
                s+= u>= l && u<=mid;
            if(s > mid - l+ 1) {
                //多出来的那个数，在 [l,mid]
                r = mid;
            }else {
                l = mid + 1;
                //在 [mid+1,r]
            }
        }
        
        return r;
    }
};