一、题目描述给定一个长度为n 1的数组nums其中所有数字都在[1, n]范围内只有一个重复的数字但可能重复多次请找出这个重复的数字。⚠️限制条件重点❌ 不能修改原数组✅ 只使用O(1)​ 额外空间示例输入nums [1,3,4,2,2] 输出2 输入nums [3,1,3,4,2] 输出3二、为什么这题“看起来简单但很难”如果你允许修改数组这题很简单方法思路问题排序相邻比较修改数组 ❌HashSet记录出现次数额外空间 ❌但题目明确要求不能改数组 O(1) 空间 于是我们必须把“数组本身”当成某种结构来推理。三、核心洞察把数组看成「链表」1️⃣ 关键抽象数组下标0 ~ n数组取值1 ~ n我们可以把数组理解成一个映射函数f(i) nums[i]从任意位置i出发不断执行i → nums[i] → nums[nums[i]] → ... 这本质上是一条链表路径2️⃣ 为什么一定有环节点数n 1值域1 ~ n没有 0➡️必然存在某个节点被指向多次➡️必然形成环而环的入口就是那个重复的数字四、Floyd 判圈算法快慢指针这正是Linked List Cycle II​ 的翻版。Step 1找相遇点快慢指针slow nums[slow] fast nums[nums[fast]]最终它们一定在环内某点相遇。Step 2找环的入口重复数将其中一个指针重置到起点slow 0然后同步前进slow nums[slow] fast nums[fast]再次相遇的位置就是重复的数字。五、结合例子理解非常关键以nums [1,3,4,2,2]为例索引路径0 → 1 → 3 → 2 → 4 → 2 → 4 → ...结构如下0 → 1 → 3 → 2 ↓ 4环2 → 4 → 2环的入口2✅ 答案就是2六、为什么这个方法一定正确阶段目的快慢指针相遇证明存在环重置一个指针对齐起点与环入口距离同步移动数学上必然在入口相遇这是一个严格可证明​ 的算法不是“玄学”。七、Java 实现面试标准版class Solution { public int findDuplicate(int[] nums) { int slow 0, fast 0; // Step 1: 找到相遇点 do { slow nums[slow]; fast nums[nums[fast]]; } while (slow ! fast); // Step 2: 找到环的入口重复数 slow 0; while (slow ! fast) { slow nums[slow]; fast nums[fast]; } return slow; } }八、复杂度分析指标数值时间复杂度O(n)空间复杂度O(1) ✅是否修改数组❌完全满足题目所有限制。九、易错点总结面试高频❗不要尝试排序 / HashMap / 计数数组错误思路原因排序修改数组HashSet额外空间二分可行但不是最优直观解✅面试加分点“这题本质是一个隐式链表 Floyd 判圈问题。”十、总结一句话解法特点暴力 / 排序❌ 不满足限制哈希表❌ 空间超限Floyd 判圈✅ 最优解记忆口诀数组当链表快慢找相遇重置再同步入口即答案