理解为什么弗洛伊德的龟兔赛跑算法在应用于整数数组时有效

我试图解决这个leetcode问题https://leetcode.com/problems/find-the-duplicate-number/ 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

现在，我确信精通离散数学的人能够直观地知道这种方法不会得出正确的解决方案，而无需首先像我一样追溯示例。

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

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

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

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

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

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

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