题目描述#

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

解题思路#

1. 链表环检测法：
   • 将数组视为链表：索引为节点，值为下一节点索引
   • 重复元素导致多指针指向同一节点形成环
2. Floyd判圈算法：
   • 快慢指针从起点出发，快指针两步，慢指针一步
   • 相遇后重置快指针，同速移动再遇点为环入口
3. 环入口即重复数：
   • 环入口节点对应多个指针指向，即重复值
4. 数学原理：
   • 设环长为L，起点到入口a步，入口到相遇点b步
   • 2(a+b) = a+b+kL → a = (k-1)L + (L-b)

代码实现#

1
/**
2
 * @param {number[]} nums
3
 * @return {number}
4
 */
5
var findDuplicate = function (nums) {
6
    let slow = 0, fast = 0;
7
    do {
8
        slow = nums[slow];
9
        fast = nums[nums[fast]]
10
    } while (slow !== fast)
11
    slow = 0;
12
    while (slow !== fast) {
13
        slow = nums[slow];
14
        fast = nums[fast]
15
    }
16
    return slow;
17
};

相似题目#

• 缺失的第一个正数
• 只出现一次的数字
• 环形链表 II
• [丢失的数字](https://leetcode.cn/problems/missing-number/
• 错误的集合