【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 <=
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums中只有一个整数出现两次或多次，其余整数均只出现一次

算法解析：

1. 构建链表逻辑：把数组的索引看作链表节点，元素值看作下一个节点的索引（因数组元素范围是[1,n]，不会越界）。由于存在重复数，链表会形成环，重复数就是环的入口节点。

2. 快慢指针找环：

   • 慢指针slow每次走 1 步，快指针fast每次走 2 步，最终会在环内某点相遇。

3. 找环的入口：

   • 从数组起点（nums[0]）和环内相遇点，同时出发两个指针（每次走 1 步），相遇处即为环的入口，也就是重复的数。

示例验证

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

• 链表结构：0 → 1 → 3 → 2 → 4 → 2（环的入口是2）。
• 快慢指针相遇后，起点指针与慢指针会在2处相遇，返回结果2。

Python代码：

from typing import List class Solution: """ 寻找数组中重复的数字（满足条件：数组长度n+1，元素范围[1,n]，仅一个重复数，可能重复多次） 核心算法：快慢指针（弗洛伊德环检测），时间复杂度O(n)，空间复杂度O(1)，不修改原数组 """ def findDuplicate(self, nums: List[int]) -> int: """ 查找数组中重复的数字 :param nums: 输入数组，长度为n+1，元素范围[1,n]，保证有且仅有一个数字重复 :return: 重复的数字 """ # 边界校验：数组长度小于2时无意义（题目保证输入合法，此处为鲁棒性补充） if len(nums) < 2: raise ValueError("数组长度至少为2") # 1. 快慢指针找环内相遇点（慢指针走1步，快指针走2步） slow = nums[0] fast = nums[0] while True: slow = nums[slow] # 慢指针：每次走1步 fast = nums[nums[fast]] # 快指针：每次走2步 if slow == fast: # 快慢指针相遇，说明存在环，退出循环 break # 2. 找环的入口（重复数就是环的入口） # 原理：从数组起点和相遇点同时出发，每次走1步，相遇处即为环入口 ptr = nums[0] # 指针1：从数组起点出发 while ptr != slow: ptr = nums[ptr] # 指针1走1步 slow = nums[slow] # 指针2（原慢指针）走1步 return ptr # -------------------------- 测试用例 -------------------------- if __name__ == "__main__": solution = Solution() # 测试用例1：基础情况 nums1 = [1, 3, 4, 2, 2] print(f"测试用例1: {nums1} → 重复数：{solution.findDuplicate(nums1)}") # 预期输出：2 # 测试用例2：重复数在开头 nums2 = [2, 2, 2, 2, 2] print(f"测试用例2: {nums2} → 重复数：{solution.findDuplicate(nums2)}") # 预期输出：2 # 测试用例3：最小边界（数组长度2） nums3 = [1, 1] print(f"测试用例3: {nums3} → 重复数：{solution.findDuplicate(nums3)}") # 预期输出：1 # 测试用例4：重复数在中间 nums4 = [3, 1, 3, 4, 2] print(f"测试用例4: {nums4} → 重复数：{solution.findDuplicate(nums4)}") # 预期输出：3

LeetCode提交代码：

class Solution: def findDuplicate(self, nums: List[int]) -> int: # 1. 快慢指针找环内相遇点 slow = nums[0] fast = nums[0] while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break # 2. 找环的入口（即重复数） ptr = nums[0] while ptr != slow: ptr = nums[ptr] slow = nums[slow] return ptr

程序运行截图展示

总结
题目要求在长度为n+1的数组中找到唯一重复的数字（元素范围[1,n]），要求不修改数组且使用O(1)空间。通过将数组视为链表（索引为节点，值为下一节点），利用快慢指针检测环：

1. 找环：快指针（每次2步）与慢指针（每次1步）相遇；
2. 找入口：从起点和相遇点同步移动，相遇点即为重复数。
   示例[1,3,4,2,2]中，链表形成环2→4→2，入口2即为解。算法时间复杂度O(n)，空间O(1)。Python代码通过双指针实现，已验证边界用例。