给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
说明：
不能更改原数组（假设数组是只读的）。只能使用额外的 O(1) 的空间。时间复杂度小于 O(n2) 。数组中只有一个重复的数字，但它可能不止重复出现一次。二分查找
class Solution { public int findDuplicate(int[] nums) { //数字的取值区间在1到len-1之间 int l = 1, r = nums.length - 1; while (l < r) { //取数字范围区间的中位数 int mid = l + (r - l) / 2; int count = 0; //遍历数组，统计小于等于中位数的数有几个 for (int num : nums) { if (num <= mid) { count++; } } //比较是否小于等于中位数的个数是否大于中位数本身，如果是，说明左区间有重复数，缩小范围至取值的左区间 if (count > mid){ r = mid; } else { l = mid + 1; } } return l; } }这道题限制太多了，并且是打算用时间换空间，不太合理，不过如果面试题嘛，那就合理了，~懂得都懂，里面牵扯的利益太多了[doge] ，咳咳，开个玩笑。 这道题第一反应就是用排序后遍历比较，不过不符合条件1，然后用set用不满足条件2，想了几个思路，要不是不满足条件，就是有bug，没想到好的思路。 然后在题解区看到liweiwei1419大佬的题解后就惊了，二分还能这么用？这道题根据大佬的题解思路完成的。另外，官方题解里有用到快慢指针，需要了解Floyd 判圈算法（龟兔赛跑算法），具体可以看这篇文章《算法-floyd判环(圈)算法》，写得很好。
快慢指针
class Solution { public int findDuplicate(int[] nums) { //因为必定存在重复值，所以fast和slow一定会相遇 //Floyd 判圈算法：除了开头位置，如果有重复值，必定在中间会相遇（即相等） int fast = 0, slow = 0; do { //慢指针走一步 slow = nums[slow]; //快指针走两步 fast = nums[nums[fast]]; //因为必定有重复值，所以只有两值相等才跳出循环 } while (fast != slow); //入环前的距离：a //把环从碰撞点分割成两段，第一段是入环点到碰撞点s1，第二段碰撞点到入环点s2 //因为找到相等值值后，快指针走的是 入环前的距离 + n圈 + n+1圈的入环点到碰撞的位置（即a+n(s1+s2)+s1）， //快指针至少比慢指针多走一圈才能碰撞，这里我们可以假设快指针只走了一圈，在第二圈的某个点和慢指针碰撞了， //那么快指针走过的距离为f=a+s1+s2+s1，而慢指针假设它一圈都没走就和快指针碰撞了，那么它走过的距离为s=a+s1， //而快指针每次走都比多一步，是慢指针的两倍，即f=2s，替换后变为f=2a+2s1，和f的原公式相减后得出：a=s2 //其实a应该等于n(s1+s2)+s2的，不过我们并不关心走了几圈，所以可以忽略 //那么再让一个指针从头出发一次循环走一步走到入环点为a，而环中的指针每次走一步，走到入环点为s2， //又根据上面得出的a=s2，那么它们就会在入环点再次碰撞。 slow = 0; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } }