快慢指针(LeetCode寻找重复数)，弗洛伊德的乌龟和兔子_快慢指针找重复的数

写此篇博客在于总结，记忆之用，欢迎评论补充。
弗洛伊德的乌龟和兔子，即快慢指针。
对于LeetCode287题，寻找重复数，题目如下：

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

 输入:[1,3,4,2,2]
 输出:2
1
2

输入:[3,1,3,4,2]
输出:3
1
2

说明：
(1)不能更改原数组（假设数组是只读的）。
(2)只能使用额外的 O(1) 的空间。
(3)时间复杂度小于 O(n^2) 。
(4)数组中只有一个重复的数字，但它可能不止重复出现一次。
这道题我们有三种思路，
方法一：排序
如果对数字进行排序，则任何重复的数字都将与排序后的数组相邻。

class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                return nums[i];
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11

复杂度分析
时间复杂度：O(nlgn)O(nlgn)。排序调用在 Java 中花费 O(nlgn)时间，因此它支配后续的线性扫描。
空间复杂度：O(1)orO(n)，在这里，我们对 nums 进行排序，因此内存大小是恒定的。如果我们不能修改输入数组，那么我们必须为 nums 的副本分配线性空间，并对其进行排序。
方法二：集合
集合就是利用set集合的性质，即set集合不能出现重复的元素。

class Solution {
    public int findDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<Integer>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return num;
            }
            seen.add(num);
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度O(n):JAVA依赖于底层的哈希表，所以插入和查找有固定的复杂度。因此，该算法是线性的，因为它由一个执行N次恒定工作的for循环组成。
空间复杂度O(n)：在最坏的情况下，重复元素出现两次，其中一次出现在数组索引n-1处，这种情况下，seen将包含n-1个不同的值，因此占用O(n)的存储空间。
方法三：弗洛伊德的乌龟和兔子(循环检测)
意此题的题干，每个数组位的和他的数字是链表的体现，至少存在一个整数是重复的，说明存在环
如果我们对于nums进行这样的解释，即对于没对索引i和值Vi而言，"下一个"Vj位于索引Vi处，可以将此问题减少到循环检测。
步骤大概为：找快慢指针交点，再把慢指针移到表头，然后两个表在此相遇的点就是环的

class Solution {
    public int findDuplicate(int[] nums) {
        // Find the intersection point of the two runners.
        int tortoise = nums[0];
        int hare = nums[0];
        do {
            tortoise = nums[tortoise];//tortoise走一步
            hare = nums[nums[hare]];//hare走两步
        } while (tortoise != hare);//如果他们不相等

        // Find the "entrance" to the cycle.
        int ptr1 = nums[0];//因为数组从0开始，所以nums是从0开始的
        int ptr2 = tortoise;
        while (ptr1 != ptr2) {
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }
        return ptr1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：O(n)
空间复杂度：O(1)

链接：https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode/来源：力扣（LeetCode）
oyd（Floyd cycle detection）

问题：如何检测一个链表是否有环，如果有，那么如何确定环的起点？如何确定环的长度？

时间复杂度：O（n） （高效率）
空间复杂度：O（1）
此算法又成为龟兔赛跑算法，基本思想是：

好比两个人在赛跑，A的速度快，B的速度慢，经过一定时间后，A总是会和B相遇，且相遇时A跑过的总距离减去B跑过的总距离一定是圈长的n倍（初中数学题……）。

弗洛伊德（Floyd ）使用了两个指针，一个慢指针（龟）每次前进一步，快指针（兔）指针每次前进两步（两步或多步效果是等价的，只要一个比另一个快就行。但是如果移动步数增加，算法的复杂度可能增加）。如果两者在链表头以外（不包含开始情况）的某一点相遇（即相等）了，那么说明链表有环，否则，如果（快指针）到达了链表的结尾（如果存在结尾，肯定无环），那么说明没环。

环的检测从上面的解释理解起来应该没有问题。接下来我们来看一下如何确定环的起点，这也是Floyd解法的第二部分。方法是将慢指针（或快指针）移到链表起点，然后两者同时移动，每次移动一步，那么两者相遇的地方就是环的起点。

下面给出论证过程：

假设一个链表是下面这样的：

设环长为n，非环形部分长度为m，当第一次相遇时显然slow指针行走了 m+An+k（A表示slow行走了A圈。附：An 是因为如果环够大，则他们的相遇需要经过好几环才相遇）。fast行走了 m+B*n+k。

上面我们说了slow每次行走一步，fast每次行走两步，则在同一时间，fast行走的路程是slow的两倍。假设slow行走的路程为S，则fast行走的路程为2S。

用fast减去slow可得：

S=（B-A）*n
1

很显然这意味着当slow和fast相遇时他们走过的路程都为圈长的倍数。

接下来，将slow移动到起点位置，如下图：

初始化额外的两个指针： ptr1 ，指向链表的头， ptr2 指向相遇点。然后，
每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口
1
2

我们利用已知的条件：慢指针移动 1 步，快指针移动 2 步，来说明它们相遇在环的入口处：（下面证明中的 tortoise 表示慢指针，hare 表示快指针）

我们注意到在这里，环的起点即为重复数

原文链接：https://blog.csdn.net/u012534831/article/details/74231581

本文为东拼西凑来的，可以点开原文看具体内容呦。
https://www.jianshu.com/p/21b4b8d7d31b这个链接有快慢指针的具体用法
快慢指针有大概三个作用：找中间值，删除倒数第n个节点，寻找环。