LeetCode 287. 寻找重复数（不修改数组 + O(1) 空间）

287. 寻找重复数 

📌 题目描述

给定一个包含 n + 1 个整数的数组 nums，其所有数字都在区间 [1, n] 范围内（包含 1 和 n）。由于数组中包含 n + 1 个数，而数的取值范围只有 n 个，因此至少存在一个重复的数。

请你返回这个唯一重复的数。

❗ 限制条件

• 不能修改数组（不能排序或哈希）

• 只使用常量级空间（不能使用额外的集合）

• 时间复杂度 < O(n²)，理想为 O(n)

🧠 解法：快慢指针（Floyd 判圈算法）

我们将数组视为一个链表，数组的下标是链表的节点编号，元素值是链表的“指针”——即跳转的位置。

例如：nums = [1, 3, 4, 2, 2]
可看作链表：
0 → 1 → 3 → 2 → 4 → 2 → 4 → 2 → ...重复数字造成了“环”，问题转换为：**找环的入口**

✅ Floyd 算法分两步：

第一步：快慢指针相遇（找环中某个点）

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]

此时 slow == fast 即为环的入口，也就是重复数字。 

✅ 完整代码 

class Solution:def findDuplicate(self, nums: List[int]) -> int:# 第一步：快慢指针相遇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)，只用了几个变量

📌 总结

• 不能修改原数组 ➜ 排除排序、计数等解法

• 要求 O(1) 空间 ➜ 排除哈希表

• 使用链表快慢指针 ➜ 经典技巧，空间压缩到极致！