LeetCode 287双指针的疑问

Question

老师，287题我就是用map来做的，因为简洁，容易想到，然后我对比了您的github上的解法，用的是双指针，只是我对您的双指针用法没看明白，希望老师解答下哈，提前给老师拜个早年 : )

Answer 1

liuyubobobo 2022-01-27 04:15:40

这里的关键是这个数组的取值范围是 1-n，整个数组有 n + 1 个数字，即索引下标是 0 - n，取值范围是 1 - n，我们可以将这个数组看做是一个“链表”。A[i] = j，表示节点 i 的下一个节点是 j。（之前的数据范围分析保证了不会越界）

所以，整个链表一共有 n + 1 个节点，n + 1 条边。所以，整个链表中一定存在且只存在一个环。并且这个环的起始位置肯定不是 0（因为 A[i] 的取值不能为 0）。因此，问题转换成了，从 0 开始出发，找到这个环的起点。（环的起点会有两条入边，对应就是有两个 A[i] 取相同的值。）

至此，这个问题完全等价于这个问题：https://leetcode-cn.com/problems/linked-list-cycle-ii/

当然，这个问题也可以直接用 map 解决。但是快慢指针可以用 O(1) 的时间解决这个问题，可以参考官方题解的方法二：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/

这个算法被称为是 floyd 循环算法。（floyd cycle finding algorithm），感兴趣可以在网上搜索这个关键词了解更多，相关 wiki 可以参考这里：https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare

继续加油！：）

• 提问者 甲骨文_0001 #1

  谢谢老师