大家好，我是吴师兄。
今天偶然间得知一个令人关注的动态：
飞书计划进行团队规模的优化调整，据悉，这一调整预计将影响大约1000名员工
。
飞书很好用，尤其是文档方面的功能，不仅免费，而且使用方便，所以我们团队的所有物料都存放在飞书里面，看到上面这个消息我们还是挺担心的，
万一这次优化调整导致文档变得和石墨一样需要收费使用
。
现在只能静观其变，慢慢地迁移资料到本地，免得到时候限制导出就麻烦了。
来做一道和「飞书」相关的算法原题。
一、题目描述
给定一个包含
n + 1
个整数的数组
nums
，其数字都在
[1, n]
范围内（包括
1
和
n
），可知至少存在一个重复的整数。
假设
nums
只有
一个重复的整数
，返回
这个重复的数
。
你设计的解决方案必须
不修改
数组
nums
且只用常量级
O(1)
的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
提示：
-
-
-
-
nums
中
只有一个整数
出现
两次或多次
，其余整数均只出现
一次
进阶：
-
-
你可以设计一个线性级时间复杂度
O(n)
的解决方案吗？
二、题目解析
题目要求我们
必须不修改数组 nums ，并且只用常量级 O(1) 的额外空间
。
一眼扫过去，题目很好理解，思路也很容易理清，
最直观的想法就是使用哈希表不就能马上查找出重复的整数么
？
但再看一眼条件，只能用常量级 O(1) 的额外空间，于是哈希表的思路走不通。
一般的解法是采取二分查找的思路来解决，这里简单给大家介绍一下操作：
1、原始数组 nums 中总共包含了 n + 1 个整数，并且这些整数都在 [1, n] 范围内，那么如果设置 n 个抽屉，1 号抽屉存放 1 号整数、2 号抽屉存放 2 号整数、以此类推，
那么总是有一个抽屉会至少存放两个数，这个数就是重复的数。
这个结论来自于抽屉原理：如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有 n + 1 个元素放到 n 个集合中去，其中必定有一个集合里至少有两个元素。
2、接下来，设置两个指针， left 指向最小值 1，right 指向最大值
nums.length - 1
，以上图为例，此时
left = 1
，
right = 4
。
3、取 left 和 right 的中间值
mid = ( left + right ) / 2
，所有的抽屉被划分为两块区间，[ left , mid ] 和 [ mid + 1 , right ]，
如果我们知道重复数字会出现在其中一块区间，那么另外一块区间根本不需要去管，不用再去存放数字
。
4、统计原始数组 nums 中小于等于 mid 元素的个数 count，此时发现
count = 3
，而 [ left , mid ] 只包含了两个抽屉，那么根据抽屉原理，必然会出现两个数挤在相同的抽屉里面。
5、因此，3 号抽屉、4 号抽屉无需再去考虑，只需要考虑 1 号抽屉、2 号抽屉，到底是哪个抽屉存放了重复的数。
6、此时，抽屉的范围发生了变化，由原来的 [ 1 , 4 ] 变成了 [ 1 , 2 ]，即 left 不变，right 变成了 2。
7、接下来，继续将 left 和 right 的区间划分为两块区间，[ 1 , 1 ] 和 [ 2 , 2 ]，此时，mid = 1 ，统计原始数组 nums 中小于等于 mid 元素的个数 count，发现 count = 1，说明 [ 1 , 1 ]这个区间只有一个抽屉一个整数，那么肯定不存在重复的数，重复的数在 [ 2 , 2 ] 这个区间。
8、此时，抽屉的范围发生了变化，由原来的 [ 1 , 2 ] 变成了 [ 2 , 2 ]，即 right 不变，left 变成了 2。
9、当前区间只有一个抽屉，也就说明是这个抽屉存放了重复的数，抽屉的编号是 2，说明重复的数字就是 2，找到答案了。
代码如下：
class Solution {
public int findDuplicate(int[] nums) {
int left = 1 ;
int right = nums.length - 1 ;
while ( left
int mid = ( left + right ) / 2 ;
int count = 0;
for ( int num : nums) {
if ( num <= mid ){
count++ ;
}
}
if ( count > mid) {
right = mid ;
}else{
left = mid + 1;
}
}
return left;
}
}
由此，这道题目也就解决了，
Don E.Knuth
不至于 24 小时还想不出来吧？
问题出在优化！
二分查找解决的代码时间复杂度是
O(nlogn)
，在面试的时候，面试官会问：
还能不能再优化一下呢？
比如，LeetCode 的留言区就有同学懊恼的记录：
今天美团面试考了这道题。作出一个解法以为完事了，结果连着追问好几种，整出翔了。
如果执着于二分查找的思路去优化，答案是无果，
优化的方向是使用快慢指针。
具体操作如下：
1、对于原始数组 nums 来说，每个数字都有其对应的
唯一索引 index
，对于每个 index ，可以将其所对应的数字作为它下一个指向的对象，将这些对象串联为链表的形式。
2、比如先选 index = 0 作为链表的起始位置，那么 index = 0 在原始数组 nums 中的对象是 1 ，因此 0 --> 1 。
3、index = 1 在原始数组 nums 中的对象是 3 ，因此 1 --> 3 ，和前面串联起来就是 0 --> 1 --> 3 。
4、index = 3 在原始数组 nums 中的对象是 2 ，因此 3 --> 2 ，和前面串联起来就是 0 --> 1 --> 3 --> 2 。
5、index = 2 在原始数组 nums 中的对象是 4 ，因此 2 --> 4 ，和前面串联起来就是 0 --> 1 --> 3 --> 2 --> 4 。
6、index = 4 在原始数组 nums 中的对象是 2 ，因此 4 --> 2 ，和前面串联起来就是 0 --> 1 --> 3 --> 2 --> 4 --> 2 。
7、在上述的图中，链表中出现了一个环，因为 index = 3 和 index = 4 的对象 nums[3] 和 nums[4] 都等于 2。
8、
链表中环的入口就是那个重复的数
，那么这道题目也就变成了寻找环入口的题目。
