287. 寻找重复数

题目描述

给定一个包含 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)，都不符合要求。

这里并不是说数组在内存中真的变成了链表，而是数组定义了一种和链表相同的“下一节点”关系。把每个数组下标看成一个节点，并定义：

next(i) = nums[i]

也就是说，下标 i 是当前节点，nums[i] 是它指向的下一个节点。对应到普通链表就是：

数组中的下标 i       <=> 链表节点 i
数组中的 nums[i]     <=> 节点 i 的 next 指针
i = nums[i]          <=> current = current.next

因为题目保证 nums[i] 的取值范围是 [1, n]，所以每个值都是合法的数组下标，可以安全地继续执行 nums[nums[i]]。每个节点又都只有一个确定的下一节点，因此从任意节点出发都会得到一条唯一的访问路径，这和沿着链表的 next 指针移动完全相同。

例如 nums = [1,3,4,2,2]，节点是数组下标，节点中保存的值表示下一步要去的下标：

下标 0 -> nums[0] = 1，所以 0 指向 1
下标 1 -> nums[1] = 3，所以 1 指向 3
下标 3 -> nums[3] = 2，所以 3 指向 2
下标 2 -> nums[2] = 4，所以 2 指向 4
下标 4 -> nums[4] = 2，所以 4 指向 2

连接起来就是：

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

数组转化为链表

注意，箭头表示的是“当前下标指向 nums[当前下标]”，并不是按照数组下标从左到右连接。

为什么从下标 0 出发一定会进入环

数组共有 0 到 n 这 n + 1 个下标，但 nums[i] 只能落在 [1, n]。因此，从下标 0 走出第一步后，指针就只能在 1 到 n 这有限的 n 个下标之间移动，而且永远不会回到 0。

如果不断执行：

current = nums[current];

访问过程可以无限继续，但可访问的下标只有有限个。根据抽屉原理，某个下标最终一定会第二次出现。由于同一个下标的下一步始终是固定的 nums[i]，从它第二次出现开始，后续路径也会不断重复，于是形成一个环。

所以，从 0 出发得到的结构一定是：

0 -> 一段不重复的路径 -> 环入口 -> 环内循环

为什么环入口就是重复数字

假设从 0 出发时，第一次被再次访问的下标是 d。第一次进入 d 和绕环后再次进入 d，必然来自两个不同的前驱下标，记作 x 和 y：

nums[x] = d
nums[y] = d
x !== y

这说明数字 d 在数组中至少出现了两次，所以 d 就是一个重复数字。同时，第一次被再次访问的位置正是环的入口。题目又保证只有一个不同的重复数字，因此这个环入口 d 必然就是题目要求寻找的重复数。

例如，nums[3] 和 nums[4] 都等于 2：

节点 3 -> 节点 2
节点 4 -> 节点 2

沿着从 0 开始的路径，第一次通过 3 -> 2 进入节点 2，之后又通过 4 -> 2 回到节点 2。因此节点 2 是环入口，而节点编号 2 也正是重复数字。

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

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) {
  // 把下标看成节点，nums[i] 表示节点 i 的下一节点。
  // 指针保存的是当前节点的下标，nums[指针] 表示沿箭头走一步。
  // 第一阶段：从 0 出发，slow 每轮走一步，fast 每轮走两步。
  // 先各移动一轮，避免都停在 0 时因 slow === fast 而直接跳过循环。
  let slow = nums[0];
  let fast = nums[nums[0]];

  while (slow !== fast) {
    slow = nums[slow]; // 沿下一节点走一步
    fast = nums[nums[fast]]; // 连续沿下一节点走两步
  }

  // 此时 slow 和 fast 在环内相遇，但相遇点不一定是环入口。
  // 设起点 0 到入口的距离为 a，入口沿箭头到相遇点的距离为 b，环长为 L。
  // 第一次相遇时 slow 走了 a + b 步，fast 走了 2(a + b) 步。
  // 两者在同一节点，路程差必然是整圈环长：a + b = k * L。
  // 因此，从相遇点再走 a 步，相对入口共走 b + a = k * L 步，恰好回到入口。
  // 第二阶段：finder 从原起点 0 出发，slow 保留在相遇点，两者都每轮走一步。
  // finder 不能改为从 nums[0] 出发，否则到入口的距离会少一步，破坏上述关系。
  let finder = 0;

  while (finder !== slow) {
    finder = nums[finder]; // 从起点前进，走 a 步后首次到达入口
    slow = nums[slow]; // 始终在环内，走 a 步后也恰好到达入口
  }

  // 为什么第一次相等的位置就是入口，而不是环内其他节点？
  // 在走满 a 步前，finder 还在环外，slow 始终在环内，不可能相等。
  // 走满 a 步时，两者同时到达入口，所以循环恰好在入口结束。
  // 入口有环外和环内两个不同的前驱，它们的 nums 值都等于入口下标，
  // 因而入口下标就是重复数字。返回 finder，而不是下一节点 nums[finder]。
  return finder;
};

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

定义三个距离：

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

图示如下：

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

环的长度是：

b + c

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

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

a + b

这里可能会有一个疑问：慢指针进入环后，有没有可能已经绕了若干圈才和快指针相遇，因此路程应该写成 a + b + q(b + c)？

答案是不会，因为这里讨论的是第一次相遇。慢指针到达环入口时，快指针一定已经在环内。此后快指针每轮走 2 步，慢指针每轮走 1 步，所以快指针相对慢指针每轮靠近 1 步。两者在环上的距离最多是一个环长，因此慢指针进入环后，不到一圈就一定会和快指针相遇。

所以，第一次相遇点到环入口的距离可以记为 b，并且满足：

0 <= b < b + c

慢指针在第一次相遇前没有完整绕环，走过的总路程就是 a + b。

如果讨论的不是第一次相遇，慢指针的路程确实应该写成：

a + b + q(b + c)

其中 q 表示额外绕环的圈数。不过这些完整的环长不会改变最终的取模关系，仍然可以得到“从相遇点走 a 步会到达环入口”的结论。

快指针走了：

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 步到达环入口，因此它们一定会在环入口相遇。

而且，这就是第二阶段的第一次相遇：在走满 a 步之前，finder 还在环外，slow 始终在环内，两者不可能指向同一个节点。因此，while (finder !== slow) 不会提前结束；当条件第一次不成立时，它们所在的位置必然是环入口。

以 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 三个额外变量，没有修改原数组。

8. 二分法

二分法和前面的链表思路不同：它不把 nums[i] 看成下一个节点，而是在数字值域 [1, n] 上进行二分查找。每次遍历数组，统计不大于中间值的元素数量，再根据统计结果判断重复数字所在的区间。

设当前区间为 [left, right]，取中间值 mid，统计数组中小于等于 mid 的数字个数 count。循环不断缩小区间，直到 left === right：

如果 count > mid，根据抽屉原理，重复数字一定在 [left, mid] 中。
如果 count <= mid，重复数字一定在 [mid + 1, right] 中。

这是因为如果 [1, mid] 中每个数字都只出现一次，那么小于等于 mid 的数字最多只有 mid 个；一旦数量超过 mid，重复数字就必然位于这个区间内。

因此，这里的二分对象是数字范围，而不是数组下标；count 是判断区间方向的依据。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function (nums) {
  // 数组长度为 n + 1，元素取值范围为 [1, n]。
  // 因此重复数字的最小可能值是 1，最大可能值是 nums.length - 1。
  // left 和 right 表示数字的取值，不是数组下标。
  let left = 1;
  let right = nums.length - 1;

  // 当 left < right 时，区间内至少还有两个候选值，需要继续缩小范围。
  // 当 left === right 时，只剩下一个候选值，不需要再次进入循环。
  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    // 统计数组中小于等于 mid 的元素数量。
    let count = 0;

    for (let i = 0; i < nums.length; i++) {
      if (nums[i] <= mid) {
        count++;
      }
    }

    // [1, mid] 中一共只有 mid 个可能的数字。
    // 如果有超过 mid 个元素落在这个范围，根据抽屉原理，
    // 重复数字一定在 [left, mid] 中。
    if (count > mid) {
      // mid 本身也可能是重复数字，因此不能写成 right = mid - 1。
      right = mid;
    } else {
      // 重复数字位于右半部分，排除 mid，
      // 继续搜索 [mid + 1, right]。
      left = mid + 1;
    }
  }

  // 循环结束时 left === right。
  // 重复数字始终位于 [left, right] 中，因此唯一候选值就是答案。
  return left;
};

这里不需要额外维护 ans：当 count > mid 时，mid 仍然可能是答案，因此保留它所在的左半区间；当循环结束时，区间中只剩下一个值，该值就是答案。

这里使用 while (left < right)，是因为更新右边界时会保留 mid：

right = mid;

当 left === right 时答案已经确定。如果使用 while (left <= right)，此时 mid === left === right，执行 right = mid 后区间不会缩小，可能陷入死循环。

复杂度分析

时间复杂度：O(n log n)。每次二分都需要遍历一次数组，二分次数是 O(log n)。
空间复杂度：O(1)。只使用了常数个变量，没有修改原数组。

9. 位运算法

除了快慢指针和值域二分，本题还可以逐个二进制位还原重复数字。

数组长度是 n + 1，数字范围是 [1, n]。对于每一个二进制位，分别统计：

nums 中该位为 1 的数字数量 numsCount。
正常范围 [1, n] 中该位为 1 的数字数量 rangeCount。

如果 numsCount > rangeCount，说明重复数字在这一位上是 1，将该位加入答案：

ans |= 1 << bit;

处理完所有二进制位后，就能得到完整的重复数字。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function (nums) {
  // 数组长度为 n + 1，元素取值范围为 [1, n]。
  const n = nums.length - 1;
  let ans = 0;
  let maxBit = 0;

  // 计算表示 n 所需要的二进制位数。
  // 例如 n = 4，二进制是 100，需要检查 3 位。
  while ((n >> maxBit) !== 0) {
    maxBit++;
  }

  // 从最低位开始，逐位判断重复数字的当前位是否为 1。
  for (let bit = 0; bit < maxBit; bit++) {
    let numsCount = 0;
    let rangeCount = 0;

    // 统计 nums 中第 bit 位为 1 的数字数量。
    for (let i = 0; i < nums.length; i++) {
      if (((nums[i] >> bit) & 1) === 1) {
        numsCount++;
      }
    }

    // 统计正常范围 [1, n] 中第 bit 位为 1 的数字数量。
    for (let num = 1; num <= n; num++) {
      if (((num >> bit) & 1) === 1) {
        rangeCount++;
      }
    }

    // nums 在当前位上多出了 1，说明重复数字的当前位是 1。
    if (numsCount > rangeCount) {
      ans |= 1 << bit;
    }
  }

  return ans;
};

为什么这个方法成立

以 nums = [1,3,4,2,2] 为例，n = 4，正常范围是 [1,2,3,4]：

逐位比较 nums 和 [1,4] 中二进制位为 1 的数量：

二进制位	`[1,4]` 中 `1` 的数量	`nums` 中 `1` 的数量	重复数字的该位
第 `0` 位	2	2	0
第 `1` 位	2	3	1
第 `2` 位	1	1	0

最终得到二进制 010，也就是十进制的 2。

边界条件与易错点

n = nums.length - 1，只需要检查到 n 的最高二进制位。
正常数字范围是 [1, n]，统计时不需要包含 0。
((num >> bit) & 1) === 1 用于判断第 bit 位是否为 1。
位运算不会修改原数组，额外空间复杂度为 O(1)。

复杂度分析

时间复杂度：O(n log n)。需要检查 O(log n) 个二进制位，每一位都要遍历 nums 和 [1, n]。
空间复杂度：O(1)。只使用了计数变量和答案变量，没有修改原数组。

#287. 寻找重复数

#题目描述

#1. 题型判断

#为什么从下标 0 出发一定会进入环

#为什么环入口就是重复数字

#2. 指针含义

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

#4. 答案更新时机

#5. 边界条件与易错点

#6. 代码实现

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

#7. 复杂度分析

#8. 二分法

#代码实现

#复杂度分析

#9. 位运算法

#代码实现

#为什么这个方法成立

#边界条件与易错点

#复杂度分析

287. 寻找重复数

题目描述

1. 题型判断

为什么从下标 0 出发一定会进入环

为什么环入口就是重复数字

2. 指针含义

3. 窗口或区间维护规则

4. 答案更新时机

5. 边界条件与易错点

6. 代码实现

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

7. 复杂度分析

8. 二分法

代码实现

复杂度分析

9. 位运算法

代码实现

为什么这个方法成立

边界条件与易错点

复杂度分析