#287. 寻找重复数

LeetCode 原题链接

#题目描述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内。

假设 nums 只有一个重复的整数，请找出这个重复的数。

要求：

• 不能修改数组 nums。
• 只使用常数级额外空间。

示例：

输入: nums = [1,3,4,2,2]
输出: 2

输入: nums = [3,1,3,4,2]
输出: 3

#1. 题型判断

本题要求在不修改数组、只使用 O(1) 额外空间的前提下寻找重复数。

如果使用排序，会修改数组或需要额外空间；如果使用 Set 记录出现过的数字，空间复杂度是 O(n)，都不符合要求。

因为数组长度是 n + 1，数字范围是 [1, n]，可以把数组看成一张链表：

下标 i 指向下一个下标 nums[i]

由于有 n + 1 个位置，却只会指向 [1, n] 中的下标，一定会形成环。重复数字就是这个环的入口。

所以本题可以转化为“链表找环入口”，使用快慢指针解决。

#2. 指针含义

把 nums[i] 看成从下标 i 出发能走到的下一个位置。

使用两个阶段的指针：

• slow：慢指针，每次走一步，即 slow = nums[slow]。
• fast：快指针，每次走两步，即 fast = nums[nums[fast]]。
• finder：第二阶段从起点 0 出发，用来和 slow 一起寻找环入口。

第一阶段让 slow 和 fast 在环内相遇。

第二阶段让 finder 从起点出发，slow 从相遇点出发，两者每次都走一步。它们再次相遇的位置，就是环入口，也就是重复数字。

#3. 窗口或区间维护规则

本题没有滑动窗口，而是维护快慢指针在“数组构成的链表”上的移动。

第一阶段：寻找环内相遇点。

slow = nums[slow];
fast = nums[nums[fast]];

当 slow === fast 时，说明快慢指针已经在环内相遇。

第二阶段：寻找环入口。

finder = nums[finder];
slow = nums[slow];

finder 从下标 0 出发，slow 从第一阶段相遇点出发。二者每次都走一步，最终会在环入口相遇。

这个入口对应的值就是重复数。

#4. 答案更新时机

本题不需要在遍历过程中不断更新答案。

答案只在第二阶段 finder === slow 时确定：

return finder;

因为指针位置本身就是重复数字。

例如 nums = [1,3,4,2,2]：

0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 -> ...

环入口是 2，所以重复数字就是 2。

#5. 边界条件与易错点

边界条件：

• 题目保证一定存在重复数，所以不需要处理“没有重复数”的情况。
• 数字范围是 [1, n]，因此从 0 出发后一定会进入合法下标范围。
• 最小规模可以是 nums = [1,1]，此时重复数字是 1。

易错点：

• 不能把 nums[i] 当成普通值来比较次数，本解法中它表示“下一个下标”。
• 第一阶段必须用快慢指针找相遇点，而不是直接判断某个值是否出现过。
• 第二阶段 finder 要从 0 开始，不是从 nums[0] 开始。
• 返回的是指针相遇的位置 finder，不是 nums[finder]。因为环入口下标就是重复数字。
• 不能排序，不能修改 nums，否则不满足题目要求。

#6. 代码实现

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

  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  let finder = 0;

  while (finder !== slow) {
    finder = nums[finder];
    slow = nums[slow];
  }

  return finder;
};

#为什么第二阶段一定在入口相遇

定义三个距离：

起点到环入口的距离 = a
环入口到第一次相遇点的距离 = b
第一次相遇点再走回环入口的距离 = c

图示如下：

起点 ---- a ----> 环入口 ---- b ----> 相遇点
                  ^                  |
                  |-------- c --------|

环的长度是：

b + c

第一阶段中，慢指针每次走 1 步，快指针每次走 2 步。

当它们第一次相遇时，慢指针走了：

a + b

快指针走了：

2(a + b)

快指针比慢指针多走的路，一定是环长度的整数倍：

2(a + b) - (a + b) = a + b

所以：

a + b = k(b + c)

其中 k 是某个正整数。

整理一下：

a = k(b + c) - b

也就是：

a = (k - 1)(b + c) + c

这表示：从相遇点出发走 a 步，等价于先绕若干圈，再走 c 步回到环入口。

所以第二阶段让：

• finder 从起点 0 出发。
• slow 从第一次相遇点出发。
• 两个指针每次都走一步。

当 finder 走了 a 步到达环入口时，slow 也刚好走了 a 步到达环入口，因此它们一定会在环入口相遇。

以 nums = [1,3,4,2,2] 为例：

0 -> 1 -> 3 -> 2 -> 4
               ^    |
               |____|

这里：

起点 0 到入口 2：0 -> 1 -> 3 -> 2，a = 3
入口 2 到相遇点 4：2 -> 4，b = 1
相遇点 4 回入口 2：4 -> 2，c = 1

环长是：

b + c = 2

并且：

a = 3 = 1 圈环长 + c = 2 + 1

所以：

finder 从 0 走 3 步：0 -> 1 -> 3 -> 2
slow 从相遇点 4 走 3 步：4 -> 2 -> 4 -> 2

它们都会到达环入口 2，所以重复数字就是 2。

#7. 复杂度分析

• 时间复杂度：O(n)。快慢指针会先进入环并相遇，第二阶段再走到环入口，总移动次数是线性的。
• 空间复杂度：O(1)。只使用了 slow、fast、finder 三个额外变量，没有修改原数组。