287. 寻找重复数

LeetCode 官方题目链接

题目描述

给定一个包含 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

提示：

• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中 只有一个 整数出现 两次或多次 ，其余整数均只出现 一次

进阶：

• 如何证明 nums 中至少存在一个重复的数字?
• 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

思路拆解

这个题目的难点在于 限制条件：

1. 不修改数组：不能排序（排序通常需要修改数组或 $O(n)$ 空间），不能使用交换索引法（像《剑指Offer》中那样）。
2. O(1) 额外空间：不能使用哈希表（Set/Map 需要 $O(n)$ 空间）。
3. O(n) 时间复杂度：不能使用双重循环暴力解法 ($O(n^2)$)。

满足这些条件的经典解法是 快慢指针 (Floyd's Tortoise and Hare) 算法，也就是 链表判圈 算法。

为什么可以转化为链表判圈？

我们将数组下标 i 视为节点，nums[i] 视为该节点指向的下一个节点的下标。 即：i -> nums[i]。

• 因为 nums 中的值都在 [1, n] 范围内，所以对于任意下标 i，nums[i] 都是一个合法的下标（不会越界）。
• 数组长度为 n + 1，下标范围是 0 到 n。
• 因为值都在 1 到 n 之间，所以 下标 0 不可能被指向（没有哪个元素的值是 0）。这意味着从下标 0 出发，我们可以进入链表，而且永远不会回到下标 0（因为没有入边）。
• 由于存在重复的数字（假设重复数为 target），这意味着至少有两个下标 i 和 j 使得 nums[i] == target 且 nums[j] == target。也就是说，有两个节点指向了同一个节点 target。这就形成了环的入口。

算法步骤

1. 第一阶段：寻找相遇点

   • 定义 slow 和 fast 指针，初始都指向下标 0。
   • slow 每次走一步：slow = nums[slow]。
   • fast 每次走两步：fast = nums[nums[fast]]。
   • 由于存在环，fast 最终一定会追上 slow（相遇）。

2. 第二阶段：寻找环入口（重复数）

   • 当 slow 和 fast 相遇时，保持 slow 在相遇点不动。
   • 将 fast（或者新建一个指针）重置回起点 0。
   • 然后让 slow 和 fast 每次都只走一步。
   • 它们再次相遇的点，就是环的入口，也就是我们要找的 重复数。

原理解释（为什么相遇点就是环入口？）

假设：

• 起点到环入口的距离为 x。
• 环入口到相遇点的距离为 y。
• 环的剩余长度为 z（即相遇点回到环入口的距离）。
• 环的总长度 L = y + z。

当 slow 和 fast 第一次相遇时：

• slow 走的距离：x + y。
• fast 走的距离：x + y + kL（fast 比 slow 多走了 k 圈）。
• 因为 fast 的速度是 slow 的两倍，所以 2 * (x + y) = x + y + kL。
• 化简得：x + y = kL -> x = kL - y。
• x = kL - y 可以写成 x = (k-1)L + (L - y)。
• 因为 L = y + z，所以 L - y = z。
• 最终得到：x = (k-1)L + z。

这意味着：从起点走到环入口的距离 x，等于从相遇点继续走 z 步（回到环入口），再加上绕环 k-1 圈的距离。

所以，当我们让一个指针从起点出发（走 x 步），另一个指针从相遇点出发（走 z 步 + 若干圈），它们最终会在 环入口 相遇。

代码实现

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

    // 1. 寻找相遇点
    // do-while 循环确保至少走一步
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);

    // 2. 寻找环入口
    // fast 回到起点
    fast = 0;
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast];
    }

    return slow;
};

运行演示

假设 nums = [1, 3, 4, 2, 2]

映射关系（下标 -> 值）：

• 0 -> 1
• 1 -> 3
• 2 -> 4
• 3 -> 2
• 4 -> 2

形成的链表路径： 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 -> ... (2 和 4 形成了一个环)

1. 第一阶段：

   • 初始：slow = 0, fast = 0
   • Step 1: slow = 1 (nums[0]), fast = 3 (nums[nums[0]] -> nums[1])
   • Step 2: slow = 3 (nums[1]), fast = 4 (nums[nums[3]] -> nums[2])
   • Step 3: slow = 2 (nums[3]), fast = 4 (nums[nums[4]] -> nums[2])
   • Step 4: slow = 4 (nums[2]), fast = 4 (nums[nums[4]] -> nums[2])
   • 相遇！相遇点是 4。

2. 第二阶段：

   • fast 重置为 0，slow 保持为 4。
   • Step 1: slow = 2 (nums[4]), fast = 1 (nums[0])
   • Step 2: slow = 4 (nums[2]), fast = 3 (nums[1])
   • Step 3: slow = 2 (nums[4]), fast = 2 (nums[3])
   • 相遇！相遇点是 2。

结果：重复数是 2。

复杂度分析

• 时间复杂度：$O(n)$。快慢指针第一阶段相遇前，指针移动次数小于链表长度。第二阶段寻找入口也是线性的。
• 空间复杂度：$O(1)$。只使用了两个指针变量 slow 和 fast。