287. 寻找重复数 (Medium)
专题归类： 12-技巧 · 二分查找 LeetCode 链接： https://leetcode.cn/problems/find-the-duplicate-number/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内（包括 1 和 n）。可知至少存在一个重复的整数。假设只有一个重复的整数，返回这个重复的数。
你设计的解决方案必须不修改数组 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
题目详细分析
数据范围： n == nums.length - 1，1 <= n <= 10^5，nums[i] 在 [1, n] 范围内
核心约束：
- 不能修改原数组（不能用排序、原地哈希等方法）
- 常量额外空间（不能用哈希表）
- 只有一个数字重复，但可能重复多次（不仅限于两次）
- 数字范围恰好是
[1, n]，长度是n+1
关键洞察：
- 这个问题的特殊之处在于数组内容和数组下标之间存在映射关系：将
nums[i]视为”下一个位置的指针”，数组就变成了一个隐式链表 - 因为有一个重复数字，所以这个隐式链表中一定存在环，而重复数字就是环的入口
- 有两种主流解法：
- Floyd 判圈法（快慢指针）—— O(n) 时间，O(1) 空间，不修改数组
- 二分查找（按值域二分）—— O(n log n) 时间，O(1) 空间，不修改数组
小白版直白理解
就像有 n+1 个孩子参加派对，每个孩子的编号在 1 到 n 之间。因为人多号少，一定有至少两个孩子编号相同。你要找出重复的编号，但不能翻看他们的名牌（不能修改数组），也不能拿纸笔记（不能用额外空间）。
方法一（快慢指针）： 想象你在玩一个”跳格子”游戏——每个格子上写着一个数字，这个数字告诉你下一步跳到哪个格子。因为有重复数字，你跳着跳着就会进入一个循环。就像在一个环形操场上跑步，跑得快的人最终会追上跑得慢的人。他们相遇的地方就在环上，然后你从起点再派一个人，两个人同步走，相遇点就是环的入口（即重复数字）。
方法二（二分查找）： 你猜一个中间数 mid，然后数一数数组中有多少个数字 ≤ mid。如果数量 > mid，说明重复数字在 [1, mid] 中；否则在 [mid+1, n] 中。就像玩”猜数字”游戏，每次缩小一半范围。
解题思路
思路一：Floyd 判圈法 / 快慢指针（推荐）
思路讲解： 将数组看作一个隐式链表——nums[i] 表示节点 i 的 next 指针指向 nums[i]。因为有重复数字，不同的下标可能指向同一个值，所以这个链表必有环，且环的入口就是重复数。
第一阶段：找相遇点。 快指针每次走两步（fast = nums[nums[fast]]），慢指针每次走一步（slow = nums[slow]），它们在环中相遇。
第二阶段：找环入口。 将慢指针重置到起点，快慢指针都每次走一步，再次相遇的位置即为环入口（重复数）。
为什么环的入口就是重复数？ 因为至少有两个不同的位置 i 和 j 满足 nums[i] == nums[j] == 重复数，这意味着从 i 和 j 出发都能到达同一个值——在链表中，这就是环的入口。
def findDuplicate(nums):
# 第一阶段：找相遇点
slow = nums[0]
fast = nums[0]
while True:
slow = nums[slow] # 走一步
fast = nums[nums[fast]] # 走两步
if slow == fast:
break
# 第二阶段：找环入口
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow # 环的入口就是重复数时间复杂度： O(n) | 空间复杂度： O(1)
思路二：二分查找（按值域二分）
思路讲解： 不是对下标二分，而是对值域 [1, n] 二分。对于 mid = (l + r) // 2，统计数组中有多少个元素 ≤ mid：
- 如果
cnt > mid，说明[1, mid]范围内有重复数（因为如果没有重复，≤ mid 的数最多只有 mid 个） - 否则，重复数在
[mid+1, n]中
这利用了鸽巢原理：n+1 个数放进 n 个抽屉，至少有一个抽屉放了两个数。
def findDuplicate(nums):
l, r = 1, len(nums) - 1 # 值域范围 [1, n]
while l < r:
mid = (l + r) // 2
# 统计 ≤ mid 的数的个数
cnt = sum(1 for x in nums if x <= mid)
if cnt > mid:
# 前 mid 个"抽屉"装入了超过 mid 个数 → 重复数在前半段
r = mid
else:
# 重复数在后半段
l = mid + 1
return l时间复杂度： O(n log n) | 空间复杂度： O(1)
思路三：位运算法
思路讲解： 按位统计。对于每一位（bit），计算数组中所有数字在该位上的 1 的个数，与 [1, n] 范围内所有数字在该位上的 1 的个数进行比较。如果数组的计数更大，说明重复数字在该位上为 1。
def findDuplicate(nums):
n = len(nums) - 1
ans = 0
bit_max = 31 # 因为 n <= 10^5，31 位足够
for bit in range(bit_max):
x = 0 # 数组第 bit 位 1 的个数
y = 0 # [1, n] 第 bit 位 1 的个数
for i in range(len(nums)):
if nums[i] & (1 << bit):
x += 1
if i >= 1 and (i & (1 << bit)):
y += 1
if x > y:
ans |= (1 << bit)
return ans时间复杂度： O(n log n)（log n 位） | 空间复杂度： O(1)
易错点
- 快慢指针的初始化：
slow = fast = nums[0]，不要初始化为 0，因为 0 不在[1, n]范围内，可能导致索引越界 - 快慢指针的步长：快指针走两步，必须写成
nums[nums[fast]]而不是nums[fast] * 2或nums[fast] + 2 - 第二阶段从
nums[0]开始：不是从 0 开始，而是从nums[0]开始（即链表头节点） - 二分法统计时注意边界：
cnt > mid是关键判断条件，不是cnt >= mid。因为如果 ≤ mid 的数的个数恰好等于 mid，说明前 mid 个数各出现一次，没有重复 - 二分法的值域范围：是
[1, n]，不是下标范围。l = 1, r = len(nums) - 1（因为nums长度为n+1，最大值为 n） - 不能使用排序：题目要求不修改数组
- 重复多次的情况：如
[3,3,3,3,3]，Floyd 判圈法和二分法都能正确处理
框架提炼
模板一：Floyd 判圈法（快慢指针找环入口）
def findCycle(nums):
# 第一阶段：快慢指针找相遇点
slow = nums[0]
fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# 第二阶段：找环入口
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow # 环的入口这个模板可以用于：
- 找链表的环入口（142-环形链表II）
- 找数组中的重复数（本题）
- 找循环数组中的重复元素
模板二：值域二分法（鸽巢原理）
def findDuplicateByRange(nums, n):
l, r = 1, n
while l < r:
mid = (l + r) // 2
cnt = sum(1 for x in nums if x <= mid)
if cnt > mid:
r = mid
else:
l = mid + 1
return l这个模板适用于已知值域范围，且元素个数大于值域大小的重复数查找问题。
关联题目
- 142-环形链表II — Floyd 判圈法的链表版本，完全相同的算法思想
- 141-环形链表 — 检测链表是否有环，Floyd 判圈法的简化版
- 41-缺失的第一个正数 — 与本题类似都是利用数组下标与值的映射关系，但用的是原地哈希
- 442-数组中重复的数据 — 找到所有出现两次的元素，用原地哈希（允许修改数组）
- 448-找到所有数组中消失的数字 — 原地哈希思想找缺失数字，与 442 互为镜像