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 才是正确。

1赞

:v:

@ding

视频已更新

看到啦,谢谢老板