快慢指针

在做到leetcode 287题时，遇到了这个问题：

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

> Input: [1,3,4,2,2]
> Output: 2
>

>

Example 2:

> Input: [3,1,3,4,2]
> Output: 3
>

>

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than O(n2).
  4. There is only one duplicate number in the array, but it could be repeated more than once.

看到了快慢指针这个解，最快能达到$O(N)$的时间复杂度，于是详细分析了一下这题。

一般会用两个指针一起遍历数组，快指针每次移动2步，慢指针每次移动1步。就跟跑步一样，假如在这个链表当中存在环的话，就快指针总是会追上慢指针，这个时候刚好超过慢指针$n$圈，并且快指针跑过的距离刚好是慢指针的两倍。

我们看图，慢指针从A开始，在B点进入了环中，经过$n$轮后，在C点和快指针相遇了。假设AB的长度是$a$，$BC$的长度是$b$，B的循环的长度是$c$，那么从B点走到C点需要经过$c-b$

此时，慢指针走过的距离是$a+nc+b​$，快指针假设是$a+Nc+​$b，因为它们速度差是2倍，所以：
$$
\begin{align}
& 2(a+nc+b)=a+Nc+b\\
\Rightarrow & a=(N-2n)c-b\\
\Rightarrow & a=(N-2n-1)c+c-b\\
\Rightarrow & a+xc=(N-2n-1+x)c+c-b
\end{align}
$$
其中，$x$可以是任意大小。

我们来解释一下上述结论：

  1. $a+xc$的意义就是，从A点出发，在B点进入循环，并经过$x$圈又回到B点
  2. $(N-2n-1+x)c+c-b$的意思则是：从C点继续向后走，走过$c-b$的长度后，回到B点，又经过$(N-2n-1+x)$圈回到B点
  3. 上述两者相同的意思是，此时指针又会共同指向B点，那么我们就找到了进入循环的点。

在题中，我们可以将数组看成一个链表，比如[1,3,4,2,2]可以看成一个$1\rightarrow3\rightarrow2\rightarrow4\rightarrow2\cdots$的链表（数组元素表示该元素指向的下一个元素的下标，如果看不懂，读代码就好）。然后我们就可以发现链表会在重复值那里进入循环，于是找到进入循环的点的时候，就可以找到重复值。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    let slow = nums[0], fast = nums[nums[0]], t = nums[0]
    while (slow != fast) {
        slow = nums[slow]
        fast = nums[nums[fast]]
    }
    slow = nums[slow]
    while (slow != t) {
        slow = nums[slow]
        t = nums[t]
    }
    return slow
};

关于快慢指针的应用

  • 单向链表是否存在循环：只要快指针和慢指针相遇，则一定存在环
  • 寻找无环链表的中位数：当快指针指向链尾时，慢指针指向链中
  • 找链表中环的入口点：如上所述
  • 两个单向无环链表是否相交：将其中一个链表首尾相连，另一个链表开始进行快慢指针遍历，就转化成了第一个问题