[287] 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]

输出：2

示例 2：

输入：nums = [3,1,3,4,2]

输出：3

示例 3：

输入：nums = [3,3,3,3,3]

输出：3

这道题和 [142] 环形链表 II 的思路如出一辙，核心都是 Floyd 判圈算法（龟兔赛跑）。

关键的观察在于：数组中的值都在 [1, n] 范围内，而数组长度为 n + 1，我们可以把每个位置 i 看作一个节点，nums[i] 看作从节点 i 指向节点 nums[i] 的一条边。这样整个数组就构成了一个「隐式链表」。由于存在重复数字，必然有两个不同位置指向同一个节点，这意味着链表中一定存在环，而环的入口就是那个重复的数字。

第一步：快慢指针找相遇点。 慢指针每次走一步 slow = nums[slow]，快指针每次走两步 fast = nums[nums[fast]]。由于存在环，两者必然会在环内某处相遇。

第二步：找环的入口。 将慢指针重置回起点 0，然后两个指针都以每次一步的速度前进，再次相遇的位置就是环的入口，即重复的数字。这一步的数学证明与 [142] 环形链表 II 完全相同：设起点到环入口距离为 a，环入口到相遇点距离为 x，则起点到环入口的距离等于快指针从相遇点走到环入口的距离，都是 a - x 步。

function findDuplicate(nums: number[]): number {
  // 慢指针每次走一格，快指针每次走两格
  let slow = 0;
  let fast = 0;

  while (true) {
    slow = nums[slow];
    fast = nums[nums[fast]];
    if (slow === fast) {
      // 快慢指针相遇，说明此时有环了
      // 用 floyd 找环，将一个指针移到头，然后两指针同时步进，相遇点即为环起点
      slow = 0;
      while (true) {
        slow = nums[slow];
        fast = nums[fast];
        if (slow === fast) break;
      }
      break;
    }
  }

  return slow;
}

这个解法非常巧妙，把数组中的「索引→值」映射抽象成链表的「节点→next」关系，将寻找重复数的问题转化为了经典的链表找环入口问题。时间复杂度 O(n)，空间复杂度 O(1)，完美满足题目的进阶要求。