P157. 查找重复数字

https://algocasts.io/episodes/QqpnglWk

 // Time: O(n), Space: O(1)
  public int findDuplicateTwoPointer(int[] nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];
    while (slow != fast) {
      slow = nums[slow];
      fast = nums[nums[fast]];
    }

    int p = 0;
    while (slow != p) {
      slow = nums[slow];
      p = nums[p];
    }
    return slow;
  }

当 slow 与 fast 相遇之后,p 指针从链表头节点开始移动,p 与 slow 每次移动一格。不太懂为什么 p 初始值被设置为 0 而不是 nums[0],目前的理解链表的头节点所在的数组下标是 0,头节点的值是 nums[0]。

@ding
抱歉这个地方我在视频里没有讲清楚,今天或明天我会在视频相应位置加个说明。

数组转换成链表后,链表的头节点是 0,你可以理解为是我们加的一个虚拟节点。所以 slow、fast、p 初始都是指向数字 0 的(这一点很重要,它们三个必须要从同一个点出发)。但是,由于这里判断相遇用的是 slow 是否等于 fast,所以如果一开始把 slow 和 fast 也初始为 0,就不会进入下面的 while 循环。因此,在进入 while 循环前,我们「手动」为 slow 和 fast 走了一次,它们本来都是 0,慢指针走一步,快指针走两步后就是:

int slow = nums[0];
int fast = nums[nums[0]];

正因如此,p 初始设置为 0 才是正确。

2赞

:v:

@ding

视频已更新

看到啦,谢谢老板

数组转链表,然后找链表开始位置,这个思路不是搞数学的能想出来吗…

@zhizx

多做些题目,就会发现,快慢指针解带环链表这种思路可以解所有以下通用表述的问题:

存在起点 S 与变换 t,t 可以将 S 变换为同类实例 S’:S’ = t(S)。我们从 S 开始,不断进行 t 变换。在有限的操作内,变换序列仅有以下两种可能:

  1. 变换结果收敛于 E
  2. 在某段子序列内循环变换

「带环链表」、「查找重复数字」和「快乐数」都可以看成上述通用表述的一个具体例子。

说人话版本: 如果某个问题中,你发现可能会出现某种循环,那么就可以考虑一下是否能用上快慢指针解法。

1赞