[NC]305. 寻找重复数

🚩传送门：牛客题目
力扣题目

题目

给定一个包含 个整数的数组 ，其数字都在 范围内（包括 和 ），可知至少存在一个重复的整数。

假设 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 且只用常量级 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2] 输出：2

示例 2：

输入：nums = [3,1,3,4,2] 输出：3

解题思路：快慢指针

本方法需要读者对 「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解，它是一个检测链表是否有环的算法 。

我们对 数组建图，每个位置 连一条 的边。由于存在的重复的数字 ，因此 这个位置一定有起码两条指向它的边，因此整张图一定存在环 。

需要注意起点 不能从无效的环开始，比如 ，这样会无限死循环。

我们先设置慢指针 和快指针 ，慢指针每次走一步，快指针每次走两步，根据「Floyd 判圈算法」两个指针在有环的情况下一定会相遇，此时我们再将 放置起点 ，两个指针每次同时走一步，相遇的点就是答案（环的入口结点）。

复杂度分析

时间复杂度：，「Floyd 判圈算法」时间复杂度为线性的时间复杂度。

空间复杂度：， 我们只需要常数空间存放若干变量。

我的代码

class Solution {
    public static int findDuplicate(int[] nums) {
        int start = 0;
        while (start == nums[start]) start++;
        int slow = start, fast = start;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = start;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}