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

方法一：哈希表

使用一个哈希表，遍历数组中的每个数，如果该数不在哈希表中，则将其加入哈希表，否则说明该数重复，直接返回即可。

时间复杂度：O(n)

空间复杂度：O(n)

方法二：二分查找

对于数组中的元素，由于它们的值都在 1∼n 的范围内，因此可以将数组划分为若干个区间，每个区间的值范围都是 [left, mid] 或 [mid+1, right]。如果整个数组中没有重复的元素，那么整个数组中的元素个数就是 n，而每个区间的元素个数都是 (mid - left + 1) 或 (right - mid)。

由于题目保证了数组中一定有重复的元素，因此可以通过统计整个数组中小于等于 mid 的元素的个数，进而判断重复元素在哪个区间中。假设整个数组中小于等于 mid 的元素个数为 count，如果 count 严格大于 mid，那么重复元素就在区间 [left, mid] 中；否则重复元素在区间 [mid+1, right] 中。这个思路类似于二分查找。

时间复杂度：O(nlogn)

空间复杂度：O(1)

代码实现：

方法一：

def findDuplicate(nums: List[int]) -> int:
    num_set = set()
    for num in nums:
        if num in num_set:
            return num
        num_set.add(num)

方法二：

def findDuplicate(nums: List[int]) -> int:
    n = len(nums)
    left = 1
    right = n - 1
    while left < right:
        mid = (left + right) // 2
        count = 0
        for num in nums:
            if num <= mid:
                count += 1
        if count > mid:
            right = mid
        else:
            left = mid + 1
    return left