1. 问题回顾与约束

• 数组长度为 $n+1$，元素都在 $[1,n]$ 的范围内。
• 因「鸽巢原理」，必存在至少一个值出现两次或以上。
• 要求：
  1. 不能 修改输入数组；
  2. 只允许 $O(1)$ 额外空间；
  3. 时间复杂度 $O(n)$。

常见但不满足约束的方法有：

• 排序后扫描（破坏原数组）；
• 哈希表或布尔标记（需要 $O(n)$ 空间）；
• 位运算统计每一位（可以不用修改数组，但实现较复杂且常数项大）；
• 值域二分（$O(n\log n)$ 时间）。

Floyd 判圈算法，恰好满足全部要求，且思路优雅。

2. 为什么能“造出”环？

把数组看成一个「从下标到下标」的映射函数：

注意下标 $i$ 与取值都在 $[1,n]$，因此：

• 从 0 出发：先访问 $f(0)=\mathrm{nums}[0]\in[1,n]$；
• 再访问 $f(f(0))=\mathrm{nums}[\mathrm{nums}[0]]$；
• ……

因为所有访问都落在 $1$ 到 $n$ 的下标上，而一共有 $n+1$ 次访问（如果一直不停），根据鸽巢原理，在下标集合 $\{1,2,\dots,n\}$ 中必有重复访问，也即在这个「链表」上存在一个环。

• 链头：下标 0
• 链身：下标 1…n，不断跳转
• 环：从某个「入口」点开始，不断指向自己或之前访问过的点

而环的入口对应的正是那个重复出现的数：

因为如果数 $x$ 被重复出现，那么在映射中就会出现两条不同的路径都指向下标 $x$，从而形成环的入口。

3. Floyd 判圈法分两步走

3.1 第一步：找相遇点（证明在环内）

• 设两个指针 slow、fast，都从 nums[0] 开始。
• 每次 slow = f(slow) 走一步，fast = f(f(fast))) 走两步。
• 如果存在环，快指针一定会在环内追上慢指针。

初始化：
    slow = f(0) = nums[0]
    fast = f(0) = nums[0]

循环直到相遇：
    slow = f(slow)
    fast = f(f(fast))
    if slow == fast: break

• 最多经过 $O(n)$ 步就能相遇。

3.2 第二步：找环的入口（就是重复的数）

• 相遇后，slow（或fast）停在环内的某个位置；
• 新建指针 ptr1 指向 起点 nums[0]，ptr2 指向相遇点 slow；
• 此后，两指针都 每次走一步，最终它们会在 环入口 相遇。

ptr1 = nums[0]
ptr2 = slow
while ptr1 != ptr2:
    ptr1 = f(ptr1)
    ptr2 = f(ptr2)

返回 ptr1  // 入口下标，即重复的数

为什么能准定位入口？

经典数学推导可参考《算法导论》中对环检测的分析，结论是：

1. 设链头到入口距离为 $a$，
2. 环长度为 $\lambda$，
3. 快慢指针在环内相遇时，慢指针已走 $a + b$ 步（其中 $b$ 是从入口再走到相遇点的距离），快指针走了 $a + b + k\lambda$ 步（快指针比慢指针多绕了 $k$ 圈）。
4. 快慢指针速度比 2:1，可得 $2(a+b) = a + b + k\lambda \implies$$a + b = k\lambda$。
5. 则 $a = k\lambda - b$，也就是从相遇点再走 $a$ 步，恰好回到入口。

因此，一根从头出发、一根从相遇点出发、同速前进，最终必在入口相遇。

4. 详细示例演示

以 nums = [3, 1, 3, 4, 2]（长度 5，取值 1…4）为例。

1. 构造映射

   下标  : 0 → 1 → 3 → 4 → 2 → 3 → …
   对应值: nums[0]=3 → nums[3]=4 → nums[4]=2 → nums[2]=3 → … 
   

   从 0 出发，很快进入了环：3→4→2→3…

2. 第一步：找相遇点

   slow 路径：0→3→2→3→2→…
   fast 路径：0→3→2→2→2→…
   相遇位置：下标 2（nums[2]=3）
   

3. 第二步：找入口

   ptr1 从头：0→3→4→2→3…
   ptr2 从相遇：2→3→4→2→…
   它们在「下标 3」相遇，对应的数值是 3
   

   因此答案是 3，正是数组中唯一重复的那个数。

代码实现

Python

def findDuplicate(nums):
    # 第一次相遇：找环内相遇点
    slow = nums[0]
    fast = nums[0]
    while True:
        slow = nums[slow]      # 慢指针走一步
        fast = nums[nums[fast]]  # 快指针走两步
        if slow == fast:
            break

    # 第二次相遇：找环的入口
    ptr1 = nums[0]
    ptr2 = slow
    while ptr1 != ptr2:
        ptr1 = nums[ptr1]
        ptr2 = nums[ptr2]
    return ptr1

# 读取输入并输出结果
if __name__ == "__main__":
    n = int(input().strip())
    nums = list(map(int, input().split()))
    print(findDuplicate(nums))

Java

import java.util.Scanner;

public class Main {
    // 寻找重复数
    public static int findDuplicate(int[] nums) {
        // 第一次相遇：找环内相遇点
        int slow = nums[0];
        int fast = nums[0];
        do {
            slow = nums[slow];          // 慢指针走一步
            fast = nums[nums[fast]];    // 快指针走两步
        } while (slow != fast);

        // 第二次相遇：找环的入口
        int ptr1 = nums[0];
        int ptr2 = slow;
        while (ptr1 != ptr2) {
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }
        return ptr1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(findDuplicate(nums));
        sc.close();
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 寻找重复数（Floyd 判圈法）
int findDuplicate(const vector<int>& nums) {
    // 第一次相遇：找环内相遇点
    int slow = nums[0];
    int fast = nums[0];
    do {
        slow = nums[slow];          // 慢指针走一步
        fast = nums[nums[fast]];    // 快指针走两步
    } while (slow != fast);

    // 第二次相遇：找环的入口
    int ptr1 = nums[0];
    int ptr2 = slow;
    while (ptr1 != ptr2) {
        ptr1 = nums[ptr1];
        ptr2 = nums[ptr2];
    }
    return ptr1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> nums(n + 1);
    for (int i = 0; i < n + 1; i++) {
        cin >> nums[i];
    }
    cout << findDuplicate(nums) << "\n";
    return 0;
}

Leetcode 100.寻找重复数-原题链接

题目描述

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

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

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

输入描述

• 第一行输入一个整数 n（$1 \leq n \leq 10^5$），表示 nums 的长度为 $n + 1$。
• 第二行输入 n + 1 个整数，表示数组 nums。

输出描述

输出 nums 中唯一的重复整数。

输入示例

4
1 3 4 2 2

输出示例

2

提示

• nums 的长度始终为 n + 1。
• nums 中的所有数字都在 [1, n] 范围内。
• nums 中 只有一个整数出现两次或多次，其余整数均只出现一次。