寻找重复数

七崽爱吃小饼干2026/07/22阅读 1

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

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

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

示例 1：

codeType

输入：nums = [1,3,4,2,2]
输出：2

示例 2：

codeType

输入：nums = [3,1,3,4,2]
输出：3

示例 3 :

codeType

输入：nums = [3,3,3,3,3]
输出：3

提示：

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中只有一个整数出现两次或多次，其余整数均只出现一次

进阶：

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

解法

解法一：二分查找

function findDuplicate(nums: number[]): number {
    // 如果用哈希表法，可以O(n)的时间复杂度和空间复杂度解决
    // 下面用二分法解决
    /**
    数组中数字范围是 [1, n]，假设我们取中间值 mid：
    统计数组中小于等于 mid 的数字个数 count；
    如果 count > mid，说明重复数在 [1, mid] 区间（因为正常情况下，1~mid 最多有 mid 个不同的数，count 超过则必有重复）；
    如果 count <= mid，说明重复数在 [mid+1, n] 区间；
    不断缩小范围，最终找到重复数。
     */
    const l = nums.length
    const n = l - 1 // 题目中有说有n+1个数字，数字范围是1-n，所以n是l - 1
    let low = 1, high = n 
    let mid
    while(low < high){
        mid = Math.floor((low + high) / 2)
        // 统计小于等于mid的数字个数
        let count = 0
        for(let i = 0; i < l; i++){
            if(nums[i] <= mid){
                count++
            }
        }
        if(count <= mid){ // 说明重复数在[mid + 1, n]
            low = mid + 1
        }else{ // 重复数在[1, mid]
            high = mid
        }
    }
    return low
};

解法二：快慢指针法

这是本题的最优解，核心是将数组映射为「链表」：数组索引 i 对应节点，nums[i] 对应节点的「下一个节点」；因为数组有重复数，所以链表必然存在环，且环的入口就是重复数（关键！）。比如数组 [1,3,4,2,2]：

索引 0 → nums [0]=1 → 索引 1；
索引 1 → nums [1]=3 → 索引 3；
索引 3 → nums [3]=2 → 索引 2；
索引 2 → nums [2]=4 → 索引 4；
索引 4 → nums [4]=2 → 索引 2； → 环：2 → 4 → 2，环的入口是 2（即重复数）。

function findDuplicate(nums: number[]): number {
     // 步骤1：快慢指针找相遇点
    let slow = 0;
    let fast = 0;
    do {
        slow = nums[slow]; // 慢指针走1步
        fast = nums[nums[fast]]; // 快指针走2步
    } while (slow !== fast);

    // 步骤2：找环的入口（重复数）
    slow = 0; // 慢指针重置到起点
    while (slow !== fast) {
        slow = nums[slow]; // 都走1步
        fast = nums[fast];
    }

    return slow; // 相遇点即为重复数
};