【Hot 100 刷题计划】 LeetCode 287. 寻找重复数 | C++ 数组判环 (快慢指针终极解法)
LeetCode 287. 寻找重复数
📌 题目描述
题目级别：中等
给定一个包含n + 1个整数的数组nums，其数字都在[1, n]范围内（包括1和n），可知至少存在一个重复的整数。
假设nums只有一个重复的整数，返回这个重复的数。
进阶要求：你设计的解决方案必须 不修改 数组nums且只用常量级O ( 1 ) O(1)O(1)的额外空间。
- 示例 1:
输入：nums = [1,3,4,2,2]
输出：2
💡 破题思路：Floyd 快慢指针 (龟兔赛跑)
题目极其变态的限制条件（不能修改原数组、只能用O ( 1 ) O(1)O(1)空间），直接封死了“排序”、“哈希表标记”、“正负号标记”等一切常规解法。
这道题的破局点在于建图。
由于数组有n + 1个元素，且所有的值都在1到n之间，这就意味着：把数组的下标作为“链表节点”，把数组里的值作为“指向下一个节点的指针 (next)”，永远不会越界！
又因为有“重复的数字”，这意味着有两个及以上的下标指向了同一个值。这就好比有多个节点指向了同一个目标节点——链表成环了，且重复的数字就是环的入口！
这道题被完美转化为了极其经典的《环形链表 II》问题，分为两步：
- 寻找环内相遇点：快指针每次走两步（
fast = nums[nums[fast]]），慢指针每次走一步（slow = nums[slow]）。由于有环，它们必然会在环内某处相遇。 - 寻找环的入口（寻找重复数）：相遇后，把慢指针调回起点（
slow = 0），快指针留在原地。此时让它们俩每次都只走一步，下一次它们再次相遇的地方，就是环的入口，也就是我们要找的重复数字！(注：此物理推导有严密的数学方程支撑)
💻 C++ 代码实现 (完全保留作者原版)
classSolution{public:intfindDuplicate(vector<int>&nums){intslow=0,fast=0;// 初始迈出第一步slow=nums[slow];fast=nums[nums[fast]];// 阶段一：龟兔赛跑，寻找环内相遇点while(slow!=fast){// 慢指针走一步，快指针走两步slow=nums[slow];fast=nums[nums[fast]];}// 阶段二：慢指针回到起点slow=0;// 两个指针以相同的速度前进，寻找环的入口while(slow!=fast){slow=nums[slow];fast=nums[fast];}// 相遇的那个数字，就是导致成环的重复数字returnslow;}};