理解为什么弗洛伊德的龟兔赛跑算法适用于整数数组

Question

我试图解决这个 leetcode 问题https://leetcode.com/problems/find-the-duplicate-number/使用我自己的龟兔算法实现，当给定以下整数数组时导致无限循环：

[3,1,3,4,2]

只有在跟踪我的算法之后，我才能看到慢速和快跑者永远不会同时接受两个重复的值。这是我的伪代码算法：

initialize fast and slow runners to 0

while(true)

   move fast runner two indices forward
   move slow runner one index forward

   if arr[fast] == arr[slow] and fast != slow
      return arr[fast] // this is the duplicate

现在，我确信精通离散数学的人能够直观地知道这种方法不会导致正确的解决方案，而不必像我那样首先跟踪一个例子。

我可以做出哪些推断或观察来让我看到这个算法行不通？我想知道如何通过一系列逻辑陈述直观地识别此逻辑中的缺陷。换句话说，为什么两个跑步者永远不会在这个例子中找到重复的解释是什么？我觉得这可能与计数有关，但我在离散方面没有很强的背景。

澄清一下，我已经查看了正确的实现，所以我知道解决它的正确方法是什么。我只是认为这种方式与将其应用于链表的工作方式过于相似，您可以将快跑者向上移动两个节点，将慢跑者向上移动一个节点。感谢您的帮助。

Answer 1

当您检测链表中的循环时，弗洛伊德的乌龟算法就会起作用。它依赖于这样一个事实：如果两个指针以不同的速度移动，它们之间的差距将继续增加到一个极限，之后如果存在循环，它将被重置。
在这种情况下，算法确实找到了一个循环，因为经过一些迭代后两个指针都收敛到索引 0。然而，您并不是要在这里检测循环；而是要检测循环。您正在尝试查找重复项。这就是为什么它会陷入无限递归：它的目的是检测循环（它正确地做到了），但在其基本实现中不检测重复项。

为了澄清这一点，这里有一个在示例数组上创建的示例链接列表。

3 -> 1 -> 3 -> 4 -> 2
'--<----<----<----<-'

如果运行 Floyd 算法，您会发现循环将在索引 0 处被检测到，因为两个指针都会在那里收敛。它的工作原理是检查fast和是否slow指向同一位置，而不是检查它们是否具有相同的节点值（fast==slow与 不同fast.value==slow.value）。

您尝试通过比较节点上的值来检查重复项，并检查节点是否不指向同一位置。这实际上是缺陷，因为弗洛伊德的算法会检查两个指针​​是否指向同一位置以检测循环。
您可以阅读这个简单、内容丰富的证明，以提高您对指针为何会收敛的直觉。