寻找重复数：Floyd判圈算法的非链表创意应用

适读人群：Java 开发者、准备算法面试的工程师 | 阅读时长：约22分钟 | 难度：Medium

---

开篇故事

2022年我在做一个数据完整性校验的服务，发现有个功能：检测一批 ID（范围限制在 1 到 n）中是否有重复，并找出那个重复的 ID。数据量在几千万条，内存非常有限。

最直观的方案是 HashSet，但内存放不下。我想到了 LeetCode 287——这不就是原题吗？

那时我刚好研究过 Floyd 判圈算法（龟兔赛跑算法），它在链表里用来检测环。但把它用在数组上——把数组当作一个函数映射 f(i) = nums[i]，从下标 0 出发，重复应用这个映射，构成一个隐式的函数链。如果存在重复数字，这个链就一定有环，重复的数字就是入环点。

这个思路当时让我脑子里"啊哈"了一下——Floyd 算法在链表里我早就会了，但第一次见到它被用在数组上，感觉像是打开了新世界的大门。

---

一、题目解析

LeetCode 287. 寻找重复数（Find the Duplicate Number）

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

边界情况 3（重复出现多次）：

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

边界情况 4（重复是 1）：

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

核心约束：

• 不能修改数组（不能排序）
• 只用 O(1) 额外空间（不能用 HashSet）
• 时间复杂度 O(n log n) 或 O(n) 均可接受

---

二、解法一：二分查找（O(n log n)）

思路分析

二分答案，不是二分数组。答案在 [1, n] 范围内，二分枚举可能的重复数字 mid。

关键：对于任意 mid，统计 nums 中 ≤ mid 的元素个数 count。如果 count > mid，说明重复数在 [1, mid] 范围内；否则在 [mid+1, n] 范围内（鸽巢原理）。

class Solution {
    public int findDuplicate(int[] nums) {
        int left = 1, right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // 统计 nums 中 <= mid 的元素个数
            int count = 0;
            for (int num : nums) {
                if (num <= mid) count++;
            }
            
            // 鸽巢原理：[1, mid] 共 mid 个位置，
            // 如果 count > mid，说明有元素被"挤"到了这个范围，重复在左边
            if (count > mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

时间复杂度：O(n log n)，二分 O(log n) 轮，每轮统计 O(n)。

空间复杂度：O(1)。

---

三、解法二：位运算（O(n)，学术价值高）

通过比较每一位上 nums 和 [1,n] 中该位为 1 的元素数量来确定答案。但这个方法在实现上比较繁琐，工程价值不高，主要是学术上展示 O(n) 时间 O(1) 空间的可行性。这里跳过，直接讲最优雅的方案。

---

四、解法三：Floyd 判圈算法（O(n)，工业级最优）

核心洞见：数组到链表的映射

把数组下标和值看作链表的"节点"和"指针"：

• 从下标 i，通过 nums[i] 到达下一个节点 nums[i]（即新下标）
• 从下标 0 开始，构成序列：0 → nums[0] → nums[nums[0]] → ...

由于数字都在 [1, n] 范围内（有效下标），且数组有 n+1 个元素，根据鸽巢原理，必然存在重复数字。重复数字 x 出现在两个不同的下标位置 i 和 j，使得 nums[i] == nums[j] == x，即两个不同的"节点"都指向同一个"节点" x。

这就构成了一个链表环，入环点就是重复数字 x！

Floyd 判圈算法两阶段：

阶段一：找相遇点

• 慢指针 slow 每次走一步：slow = nums[slow]
• 快指针 fast 每次走两步：fast = nums[nums[fast]]
• 当 slow == fast 时，找到相遇点（在环内某处）

阶段二：找入环点（重复数字）

• 将 slow 重置到起点 0，fast 留在相遇点
• 两者都每次走一步
• 再次相遇时，位置就是入环点，即重复数字

数学证明： 设链表头到入环点的距离为 a，入环点到相遇点的距离为 b，环的周长为 c。

• 慢指针走了 a + b 步
• 快指针走了 a + b + k×c 步（多走了 k 圈）
• 快指针步数是慢指针的 2 倍：2(a+b) = a+b+kc，即 a+b = kc
• 因此 a = kc - b = (k-1)c + (c-b)

从相遇点到入环点的距离恰好是 c-b，加上 (k-1) 整圈就是 kc-b，等于 a。所以从起点和从相遇点同时出发，走相同步数后会在入环点相遇。

算法流程

完整 Java 代码

class Solution {
    public int findDuplicate(int[] nums) {
        // 阶段一：找相遇点
        int slow = nums[0];
        int fast = nums[nums[0]];
        
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        
        // 阶段二：找入环点（重复数字）
        slow = 0;
        // fast 留在相遇点
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];  // 此阶段 fast 也是每步走一格
        }
        
        return slow;  // 或 fast，此时 slow == fast == 重复数字
    }
}

复杂度分析

时间复杂度：O(n)

阶段一：慢指针最多走 n 步（环的周长 ≤ n），快指针最多走 2n 步。阶段二：最多走 n 步。总体 O(n)。

空间复杂度：O(1)

只用了两个指针变量。

我在 LeetCode 提交，运行时间 3ms，击败 99.2% 的 Java 用户。

---

五、举一反三

同类型题目

LeetCode 142. 环形链表 II

在真正的链表中找环的入口节点。Floyd 算法的直接应用，本题把数组当链表来用，两者算法框架完全相同。

LeetCode 141. 环形链表

只判断链表是否有环（不需要找入口）。Floyd 算法第一阶段。

LeetCode 268. 丢失的数字

[0, n] 中缺失的那个数。用数学方法（期望总和 - 实际总和）O(n) O(1) 解决。

LeetCode 645. 错误的集合

找出数组中重复的数字和缺失的数字。排序后线性扫描，或者利用下标映射。

各解法对比

解法	时间	空间	修改数组	适用场景
HashSet	O(n)	O(n)	否	空间充裕时最简单
排序	O(n log n)	O(1)~O(n)	是	允许修改时
二分答案	O(n log n)	O(1)	否	面试常用
Floyd	O(n)	O(1)	否	最优，面试加分

---

六、踩坑实录

坑一：Floyd 阶段一的初始化

现象： 某些输入下，slow 和 fast 在第一步就相等了，然后直接进入阶段二，但结果不对。

原因： 如果 slow 和 fast 从同一个点出发（都从 0 出发），第一步就可能满足 slow == fast（如果 nums[0] == 0，虽然题目约束数字在 [1,n] 不包含 0，但需要注意）。

更安全的写法是让 slow 和 fast 先走一步再进入循环（do-while），或者使 slow 从 nums[0] 出发，fast 从 nums[nums[0]] 出发（如代码所示），这样初始时 slow != fast（除非 nums[0] == nums[nums[0]]，那它们一步后也会相等，循环直接结束也对）。

解法： 按照代码里的写法：slow 初始化为 nums[0]，fast 初始化为 nums[nums[0]]，然后判断 while(slow != fast)，这样避免了从同一点出发的问题。

坑二：阶段二中 fast 的步长

现象： 阶段二结果不对，找到的不是重复数字。

原因： 阶段二中，slow 和 fast 都应该每次走一步（slow = nums[slow], fast = nums[fast]），而不是 fast 还是走两步。很多人忘记了阶段二和阶段一的移动速度不同。

解法： 阶段一：fast 走两步（fast = nums[nums[fast]]）；阶段二：fast 走一步（fast = nums[fast]）。

坑三：binary search 的 count 逻辑

现象： 二分解法在某些输入（重复数字为 n）时返回结果不对。

原因： 统计 count 时用的是 num <= mid，当重复数字是 n 时，mid 最终等于 n，count 统计 ≤ n 的元素个数 = n+1（所有元素），n+1 > n，正确更新 right = mid = n。继续循环直到 left == right == 重复数字。但如果统计逻辑用了 num < mid 而不是 num <= mid，就会差一位。

解法： 统计时用 num <= mid，这是鸽巢原理的正确表达：[1, mid] 有 mid 个位置，count > mid 说明有重复。

---

七、总结

LeetCode 287 是我见过的把 Floyd 判圈算法用在非链表场景最漂亮的例子。通过构造"下标到值"的映射函数，把数组问题转化为链表环问题，然后用 Floyd 算法 O(n) O(1) 完美解决。

三条核心要点：

1. 数组到链表的映射是这道题的关键洞见：把 f(i) = nums[i] 看作从下标 i 到下标 nums[i] 的"指针跳转"，重复数字的存在使这个序列必然出现环，入环点就是重复数字。

2. Floyd 算法两阶段：第一阶段找相遇点（快指针走两步），第二阶段找入环点（两指针都走一步）。第二阶段的数学基础是"从起点和从相遇点走相同步数会在入环点相遇"。

3. 阶段一初始化时 slow 和 fast 不从同一位置出发，防止第一步就误判为相遇。

延伸思考：

Floyd 算法的本质是利用"步长不同"来检测循环。这个思路在函数迭代中普遍适用：如果一个函数的迭代序列存在循环，慢步+快步一定会相遇，入环点可以用第二阶段确定。这在密码学（Pollard 的 rho 算法分解大整数）、伪随机数检测等领域都有应用。