寻找重复数 图解题解

寻找重复数的约束为什么这么苛刻

题目给一个长度为 n+1 的数组，每个元素都在 1 到 n 之间，由抽屉原理必然存在重复的数，要求把它找出来。真正定难度的是三条枷锁：不能修改原数组、只准用 O(1) 额外空间、不能上 O(n²) 暴力。三条一叠加，常规兵器几乎全部报废，这道题考的就是在夹缝里找出路。

为什么排序和哈希表都被判了死刑

先排序再找相邻相等的元素，思路没错，但排序会改动原数组，直接违反「不能修改数组」的规定。开一个哈希集合或计数数组记录出现次数，一遍扫描就能揪出重复，但那是 O(n) 的额外空间，同样超标。两层循环逐对比较倒是零空间零改动，可惜 O(n²) 被明令禁止。三条常规路全部堵死之后，只能换一个视角重新看这个数组。

数组怎么就变成了一条有环链表

关键观察：把每个下标看成一个节点，让它连一条边指向「以自己存的值为下标」的那个节点，整个数组就成了一张每个点只有一条出边的图。从下标 0 出发一路往下跳，节点有限、每步都有路可走，最终必然绕进一个圈。而「两个不同下标存着同一个值」恰好意味着两条边汇入同一个节点——被汇入的那个节点就是环的入口，它对应的数正是重复数。

还有一个细节保证从下标 0 出发是安全的：所有元素都不小于 1，没有任何边指向下标 0，所以 0 是纯粹的起点，不可能本身就困在环里。找重复数，就这样被严格翻译成了链表的「找环入口」，也就是 LeetCode 142 环形链表 II 的老问题。

快慢指针两个阶段各自在干什么

第一阶段，slow 每次跳一步（走到 nums[slow]），fast 每次跳两步。两个指针都进环之后，fast 每轮比 slow 多走一步，彼此距离每轮缩短一，不存在跳过对方的可能，所以一定会在环内某点相遇——相遇只证明有环，位置通常不是入口。

第二阶段，把 slow 拉回起点，两个指针改成同速各走一步。设起点到入口的距离为 a、入口到相遇点为 b、环长为 c。相遇时 fast 的路程恰好是 slow 的两倍，把等式化简可以得到：a 等于「从相遇点继续走到入口」的距离再加上若干整圈。于是一个从头出发、一个从相遇点出发，同速走 a 步后必然同时踩在环入口上，返回它即可。

复杂度是多少，哪里最容易写错

两个阶段的指针路程都不超过链长加环长，总时间 O(n)；全程只用 slow、fast 两个下标变量，空间 O(1)，原数组一个元素都没动，三条约束全部满足。

三个常见的坑：一是 fast 忘了写成 nums[nums[fast]]，只走一步就永远追不上 slow，死循环；二是第二阶段忘记把 slow 拉回起点，找到的不是环入口，答案直接错；三是两个指针从同一起点出发，必须先各走一步再判断相等，先判断会被起点的假相遇骗过。

Python

def findDuplicate(nums):
    slow = fast = 0
    # 阶段一：快慢指针在环里相遇
    while True:
        slow = nums[slow]          # 慢走 1 步
        fast = nums[nums[fast]]    # 快走 2 步
        if slow == fast:
            break
    # 阶段二：slow 回起点，齐步走找环入口
    slow = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow                    # 环入口 = 重复数

C++

int findDuplicate(vector<int>& nums){
    int slow = 0, fast = 0;
    do {                       // 阶段一：相遇
        slow = nums[slow];          // 慢 1 步
        fast = nums[nums[fast]];    // 快 2 步
    } while(slow != fast);
    slow = 0;                  // 阶段二：找入口
    while(slow != fast){
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;               // 重复数
}

Java

public int findDuplicate(int[] nums) {
    int slow = 0, fast = 0;
    do {                       // 阶段一：快慢相遇
        slow = nums[slow];          // 慢走 1 步
        fast = nums[nums[fast]];    // 快走 2 步
    } while (slow != fast);
    slow = 0;                  // 阶段二：齐步找入口
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;               // 环入口 = 重复数
}