你设计的解决方案必须 不修改 原数组，且只用常量级 O(1) 的额外空间。
进阶：
- 如何证明
nums中至少存在一个重复的数字？ - 你可以设计一个线性级时间复杂度
O(n)的解决方案吗？
寻找重复数 - 二分
定义 表示 nums 数组中小于等于 i 的数有多少个，假设重复的数是 target，那么 里的所有数满足 ， 里的所有数满足 ，具有单调性，可以二分
func findDuplicate(nums []int) int {
n := len(nums)
left, right := 0, n - 1
ans := -1
for left <= right {
mid := left + (right - left) >> 1
count := 0
for _, num := range nums {
if num <= mid {
count++
}
}
if count <= mid {
left = mid + 1
} else {
right = mid - 1
ans = mid
}
}
return ans
}寻找重复数 - 二进制
将所有数二进制展开按位考虑如何找出重复的数，如果能确定重复数每一位是 1 还是 0 就可以按位还原出重复的数是什么
考虑第 i 位，记数组中二进制展开后第 i 位为 1 的数有 个，数字 这 n 个数二进制展开后第 i 位为 1 的数有 y 个，那么当且仅当 时，重复的数第 i 位为 1
func findDuplicate(nums []int) int {
n := len(nums)
ans := 0
for bit := 0; bit < 32; bit++ {
x, y := 0, 0
for i := 0; i < n; i++ {
if nums[i] & (1 << bit) != 0 {
x++
}
if i > 0 && i & (1 << bit) != 0 {
y++
}
}
if x > y {
ans |= 1 << bit
}
}
return ans
}寻找重复数 - 快慢指针
预备知识
本方法需要对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解，它是一个检测链表是否有环的算法，相关例题有 环形链表
思路和算法
对数组建图，每个位置 i 连一条 的边。由于存在重复的数字 target，因此 target 这个位置一定有起码两条指向它的边，因此整张图一定存在环，且要找到的 target 就是这个环的入口，那么整个问题就等价于 142.环形链表 II
func findDuplicate(nums []int) int {
slow, fast := 0, 0
for slow, fast = nums[slow], nums[nums[fast]]; slow != fast; slow, fast = nums[slow], nums[nums[fast]] { }
slow = 0
for ; slow != fast; slow, fast = nums[slow], nums[fast] { }
return slow
}