287. 寻找重复数

力扣题目链接 (opens new window)

题目描述

给定一个包含 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

提示：

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

进阶：

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

思路

暴力解法是用哈希表记录出现过的数字，时间O(n)，空间O(n)。但题目要求空间O(1)。

如果可以修改数组，可以排序后遍历，或者原地标记。但题目不允许修改数组。

本题有两种巧妙的解法：

方法一：快慢指针（推荐）

这是本题最精妙的解法。核心思路：把数组看作链表，重复的数字就是环的入口。

为什么可以看作链表？

因为数组的值都在 [1, n] 范围内，而数组有 n+1 个元素，下标是 [0, n]。

可以把 nums[i] 看作指向 nums[nums[i]] 的"指针"。

比如 nums = [1,3,4,2,2]：

• 从下标 0 出发：0 → 1 → 3 → 2 → 4 → 2 → 4 → 2 → ...
• 形成了环：2 → 4 → 2

重复的数字 2，就是环的入口！

这样就转化成了 142. 环形链表 II 的问题。

用快慢指针找环的入口：

1. 快慢指针都从下标 0 开始（或者任意起点，但不能从重复数字本身开始）
2. 慢指针每次走一步：slow = nums[slow]
3. 快指针每次走两步：fast = nums[nums[fast]]
4. 相遇后，一个指针回到起点，两个指针都每次走一步，再次相遇就是环的入口

为什么从下标 0 开始？

因为下标 0 一定不是环的入口（重复的数字在 [1, n]，而 0 不在）。

方法二：二分查找

把"值域"进行二分。

统计数组中 ≤ mid 的数字个数 count：

• 如果 count > mid，说明 [1, mid] 中有重复数字
• 否则，重复数字在 [mid+1, n]

不断缩小范围，最后找到重复数字。

时间复杂度O(n log n)，空间O(1)。

下面用方法一（快慢指针）实现。

模拟过程

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

下标：  0  1  2  3  4
值：    1  3  4  2  2

映射关系：
0 → nums[0]=1 → nums[1]=3 → nums[3]=2 → nums[2]=4 → nums[4]=2 → nums[2]=4 → ...
形成环：2 → 4 → 2

第一阶段：快慢指针相遇

• slow=0, fast=0
• slow=1, fast=3
• slow=3, fast=4
• slow=2, fast=2（相遇）

第二阶段：找环入口

• 一个指针回到0，另一个在2
• 都每次走一步：0和2 → 1和4 → 3和2 → 2和2（再次相遇）
• 入口是2，即重复的数字

解题代码

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        
        // 第一阶段：快慢指针相遇
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        
        // 第二阶段：找环入口
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;
    }
};

复杂度分析

• 时间复杂度：O(n)，最多遍历两遍数组
• 空间复杂度：O(1)，只用了两个指针

其他语言

Python3

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = 0
        
        # 第一阶段：快慢指针相遇
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        
        # 第二阶段：找环入口
        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        
        return slow

Java

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        
        // 第一阶段：快慢指针相遇
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        
        // 第二阶段：找环入口
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return slow;
    }
}

Go

func findDuplicate(nums []int) int {
    slow, fast := 0, 0
    
    // 第一阶段：快慢指针相遇
    for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }
    
    // 第二阶段：找环入口
    slow = 0
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }
    
    return slow
}

JavaScript

var findDuplicate = function(nums) {
    let slow = 0, fast = 0;
    
    // 第一阶段：快慢指针相遇
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);
    
    // 第二阶段：找环入口
    slow = 0;
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    
    return slow;
};

二分查找解法

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int left = 1, right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = 0;
            
            // 统计 <= mid 的数字个数
            for (int num : nums) {
                if (num <= mid) count++;
            }
            
            if (count > mid) {
                right = mid; // 重复数字在 [left, mid]
            } else {
                left = mid + 1; // 重复数字在 [mid+1, right]
            }
        }
        
        return left;
    }
};

与代码随想录联系

本题用快慢指针解，非常巧妙，和 142. 环形链表 II 是同样的思路。

关键洞察：把数组看作隐式链表，数组的值就是"指针"。

在代码随想录的链表章节中，详细讲解了快慢指针找环的原理和证明。

录友们如果对快慢指针还不熟悉，建议先做链表的环检测题，再来理解本题会更容易。

本题也可以用二分查找解，但需要统计个数，时间复杂度O(n log n)。快慢指针解法更优，时间O(n)，空间O(1)，满足所有要求。

为什么一定有环？

因为数组有 n+1 个元素，值在 [1, n]，根据抽屉原理（鸽巢原理），一定有重复的数字。

而下标 0 不会被任何 nums[i] 指向（因为 nums[i] ≥ 1），所以 0 是"入口"，从 0 开始一定会进入环，且环的入口就是重复的数字。