本题要求在不修改原数组且仅使用常数级 O(1) 额外空间的前提下在包含 n 1 个整数数值范围在 [1, n]的数组中找出那个唯一的重复整数。解决该问题的终极方案是将数组隐式抽象为一个单向有向图或单链表将数组下标i视为图节点将nums[i]视为从节点i指向节点nums[i]的有向边。由于数组元素的数值都在 [1, n] 范围内下标0绝对不会被任何节点指向即入度为 0这保证了从下标0出发构成的路径必然是一条形如ρRho字型的带环链表。在该拓扑结构中重复的整数正是环的入口节点。利用Floyd 弗洛伊德判圈算法快慢指针法可以在 O(n) 时间复杂度和 O(1) 空间复杂度下精准定位环入口完美满足题目所有苛刻约束。一、 问题的数学本质与拓扑图结构抽象1.1 题目物理约束与图论转换题目给出的条件包含极强的拓扑暗示数组nums的长度为n 1下标有效范围为[0, n]。数组中存储的所有元素数值均在[1, n]范围内。数组中存在且仅有一个重复的整数可能重复 2 次或多次其余数字各出现 1 次。如果我们将数组下标看作图的节点编号将数组中保存的值看作指针/有向边就可以建立如下映射关系节点 i ------有向边------ 节点 nums[i]这种每个节点有且仅有一条出边的图在图论中被称为映射图Functional Graph或基环内向树集合。索引下标 (Index): 0 1 2 3 4 数组数值 (Value): [ 1, 3, 4, 2, 2 ] 对应的有向图映射关系: 0 - nums[0] (1) 1 - nums[1] (3) 3 - nums[3] (2) 2 - nums[2] (4) 4 - nums[4] (2)绘制成拓扑拓扑图后结构如下0 --- 1 --- 3 --- 2 --- 4 ^ | |_______|1.2 为什么从下标 0 出发必然存在环出度确定性因为数组中的每一个位置i都存储着一个有效的数值nums[i]所以从任何一个下标出发都有且仅有一条出边出度 Out-degree 1。节点有限性图共有n 1个节点下标 0 到 n。从任意节点出发持续沿着边走根据抽屉原理走过n 1步之后必然会重复经过某个此前已访问过的节点因此图中必定包含至少一个环。起点 0 的特殊性因为所有元素的值nums[i]满足1 nums[i] n这意味着没有任何索引的数值会是 0。用图论术语来说节点 0 的入度In-degree严格为 0。因此节点 0 绝对不可能位于任何环内部它必定是环外链条的起始点1.3 为什么环的入口节点就是重复的整数入度代表有多少个节点指向当前节点。 如果有两个或多个不同的下标i和ji ! j它们内部保存了相同的数值X即nums[i] nums[j] X这意味着在图论物理结构中节点 i 和节点 j 都存在一条有向边指向节点 X。这就导致节点 X 的入度大于等于 2在每个节点出度均为 1 的单向图拓扑中当一条从环外延伸进来的链条接入环中时接合处的节点即环的入口节点必然同时接收来自环外链条的边和来自环内循环的边因此环入口节点的入度必然大于等于 2。结论起点 0 所在的单向图路径中环的入口节点对应的编号就是数组中重复的那个整数二、 弗洛伊德判圈算法 (Floyds Cycle-Finding Algorithm) 严格数学推导为了在不修改数组且不使用额外空间的情况下找到环的入口算法分为两个阶段阶段一碰撞检测与阶段二环入口定位。2.1 拓扑几何模型与符号定义假设从起点0到环入口节点的距离为a从环入口节点到快慢指针首次相遇点的距离为b环的完整周长为L相遇点顺时针走完剩余环回到入口的距离为c因此满足b c L。拓扑示意图如下起点 (0) -------- 距离 a -------- 环入口 (Entry) -------- 距离 b -------- 相遇点 (Meet) ^ | |-------------- 距离 c -----------------| |-------------- 环周长 L --------------|2.2 阶段一检测环与相遇点推导设置两个指针慢指针slow每次沿有向边走 1 步即slow nums[slow]快指针fast每次沿有向边走 2 步即fast nums[nums[fast]]由于快指针相对慢指针的速度差为 1一旦快慢指针都进入环中快指针每走一步就会缩短与慢指针之间 1 个单位的距离。因此快慢指针必然会在环内的某个位置相遇。假设相遇时慢指针slow走的总步数为S快指针fast走的总步数为F因为快指针的速度是慢指针的 2 倍且两者同时出发所以有F 2 * S慢指针在相遇时从起点走到环入口距离a然后在环内走了距离b可能绕了k1圈S a b k1 * L快指针在相遇时从起点走到环入口距离a然后在环内走了距离b绕了k2圈F a b k2 * L代入F 2 * S关系式中a b k2 * L 2 * (a b k1 * L)化简等式a b (k2 - 2 * k1) * L令整数k k2 - 2 * k1由于快指针比慢指针至少多绕环若干圈k 1得到核心方程a b k * L将a孤立在方程左侧a k * L - ba (k - 1) * L (L - b)因为b c L所以L - b c。代入上式得到a (k - 1) * L c2.3 阶段二环入口定位推导方程a (k - 1) * L c揭示了一个极具美感的几何性质从起点走到环入口的距离a恰好等于从相遇点绕环k - 1圈后再走距离c即到达环入口的距离基于此结论算法进入阶段二保持慢指针slow位于相遇点不变。引入一个新指针head将其重置回起点0。让head和slow以相同的速度每次走 1 步同时向前推进。当head走了a步到达环入口时slow也向前走了a步。而slow从相遇点出发走a步相当于走过了c距离回到环入口再加上绕环k - 1圈最终也必定精准停在环入口节点处此时head与slow指向的节点编号相同该编号即为环的入口也就是数组中的重复元素。三、 多种解法维度对比与选型评估针对 LeetCode 287常见的解决思路有多种下表从时间复杂度、空间复杂度、是否修改原数组、是否满足题目约束等维度进行全面对比解法名称时间复杂度空间复杂度修改原数组是否符合题目约束核心原理物理瓶颈 / 缺点暴力双重循环O(n^2)O(1)否否超时枚举每一个元素在后续元素中查找是否存在重复时间复杂度极高当 n 10^5 时引发严重超时原地排序O(n log n)O(1) 或 O(n)是否违反约束排序后相邻元素比较若nums[i] nums[i1]则为重复数破坏了原数组的物理结构违反“不修改数组”约束哈希表 / Visited 数组O(n)O(n)否否违反约束遍历数组记录已访问的数字遇到重复即返回需要申请 O(n) 的额外内存空间违反“常数空间”约束原地标记法取反/交换O(n)O(1)是否违反约束利用nums[abs(x)]取反作为访问标记或将数值交换到对应下标写入操作修改了原数组物理内容违反“不修改数组”约束二分查找按数值范围O(n log n)O(1)否是统计区间[1, mid]内的数字个数利用抽屉原理逼近重复值耗时相对较长包含 O(log n) 次全数组扫描位运算按位统计O(n log n)O(1)否是逐位统计 1 到 n 与 nums 中二进制各位置 1 的个数逻辑较为繁琐需要对比 32 个二进制位Floyd 判圈算法当前解法O(n)O(1)否是全局最优解将数组抽象为隐式图快慢指针求环入口无缺点完美契合所有时空及无修改约束四、 算法执行状态机步进追踪 (Step-by-Step State Machine Trace)为了彻底厘清指针在内存中的演进过程下面提供两个典型示例的全量状态追踪。4.1 示例 1nums [1, 3, 4, 2, 2]数组规模n 4节点集合{0, 1, 2, 3, 4}隐式图映射关系nums[0] 1节点 0 - 节点 1nums[1] 3节点 1 - 节点 3nums[2] 4节点 2 - 节点 4nums[3] 2节点 3 - 节点 2nums[4] 2节点 4 - 节点 2路径形态0 - 1 - 3 - 2 - 4 - 2 ...环为2 - 4 - 2入口为2阶段一快慢指针碰撞检测slow每次 1 步fast每次 2 步步骤 (Step)slow 探针位置slow 节点值 (nums[slow])fast 探针位置fast 节点值 (nums[fast])判定分支 (slow fast)初始0101循环启动Step 1131 - 32 (nums[3])3 ! 2继续Step 2322 - 42 (nums[4])2 2触发碰撞相遇点锁定为节点2。阶段二寻找环入口重置head 0slow保持在相遇点2均每次走 1 步步骤 (Step)head 指针位置head 节点值 (nums[head])slow 指针位置slow 节点值 (nums[slow])判定分支 (head slow)初始01240 ! 2继续Step 113421 ! 4继续Step 232243 ! 2继续Step 3244 - 24 - 22 2锁定环入口最终返回重复数2。4.2 示例 2nums [3, 1, 3, 4, 2]数组规模n 4节点集合{0, 1, 2, 3, 4}隐式图映射关系nums[0] 3nums[1] 1(孤立自环起点 0 无法触及)nums[2] 3nums[3] 4nums[4] 2路径形态0 - 3 - 4 - 2 - 3 ...环为3 - 4 - 2 - 3入口为3阶段一快慢指针碰撞检测步骤 (Step)slow 探针位置slow 节点值fast 探针位置fast 节点值判定分支初始0303循环启动Step 1343 - 42 (nums[4])4 ! 2继续Step 2422 - 34 (nums[3])2 ! 4继续Step 3234 - 23 (nums[2])3 3触发碰撞相遇点锁定为节点3。阶段二寻找环入口步骤 (Step)head 指针位置head 节点值slow 指针位置slow 节点值判定分支初始03340 ! 3继续Step 1343 - 423 3锁定环入口最终返回重复数3。五、 源码实现与逐行硬核注释class Solution { public int findDuplicate(int[] nums) { // 初始化慢指针 slow 与快指针 fast起点均为图的源头节点 0 int slow 0; int fast 0; // 初始化头指针 head用于阶段二定位环入口 int head 0; // 阶段一图的环内碰撞检测 while (true) { // 慢指针向前步进 1 步沿着当前下标对应的数值作为目标下标跳转 slow nums[slow]; // 快指针向前步进 2 步连续跳转两次 fast nums[nums[fast]]; // 检查快慢指针是否在环内相遇 if (slow fast) { // 阶段二定位环入口节点即重复的数值 // 保持 slow 在相遇点head 从起点 0 出发两者均以步长 1 同步推进 while (head ! slow) { slow nums[slow]; // slow 步进 1 步 head nums[head]; // head 步进 1 步 } // 当 head 与 slow 再次相遇时当前节点编号即为环入口也就是重复元素 return slow; } } } }六、 复杂度分析与底座硬件/编译器优化视角6.1 时间复杂度O(n)阶段一碰撞检测慢指针进入环所需步数不超过n。进入环后快指针与慢指针之间的相对距离不超过环长LL n。快指针每走一步相对距离缩短 1 个单位因此相遇所需的步数严格小于n。阶段一的总步数不超过2 * n。阶段二环入口定位head从0走到环入口所需的步数为aa n。阶段二的总步数为a。总时间复杂度T(n) 2 * n n 3 * n O(n)。整体算法时间开销与数组规模呈 strictly 线性关系。6.2 空间复杂度O(1)算法仅定义了slow、fast和head3 个标量整型变量存放在 JVM 方法调用的栈帧局部变量表中。没有申请任何堆内存、动态数组、哈希表或递归栈空间。空间复杂度为绝对的O(1)。6.3 CPU Cache 与分支预测硬件级表现虽然 Floyd 判圈算法在渐进时间复杂度上达到了最优的 O(n)但在底层硬件执行效率上存在特定的性能特征1. 数组随机访问与 L1/L2 Cache Miss缓存未命中普通数组遍历如线性扫描for (int i 0; i n; i)具有极佳的空间局部性Spatial Locality。CPU 的硬件预取器Hardware Prefetcher能够顺畅地将连续的 64 字节 Cache Line 加载进 L1 Data Cache。但在本算法中指针跳转形式为slow nums[slow]。这是一种典型的指针追逐Pointer Chasing模式。内存访问顺序取决于数组中保存的具体数值呈现乱序/随机跳转特征。当数组规模较大如n 10^5占内存约 400KB超出 32KB 的 L1 Data Cache 容量时频繁的非连续跳转会导致较高的L1/L2 Data Cache Miss Rate。CPU 流水线会因为等待主存数据加载Memory Latency而产生停顿Stall。2. 分支预测Branch Prediction表现外层while (true)循环迭代次数极少在n 10^5规模下通常数十至数千次即相遇CPU 的分支预测器Branch Predictor可以轻松实现接近 100% 的预测准确率。内层head ! slow循环单向线性推进分支指令方向高度一致分支预测失败Branch Misprediction Penalty的开销几乎可以忽略不计。七、 抽屉原理与图论存在性严密证明 (进阶解答)题目进阶部分提出了两个核心问题如何证明nums中至少存在一个重复的数字能否设计一个线性级时间复杂度 O(n) 的解决方案第二个问题已通过上述 Floyd 算法解答。以下对第一个问题进行形式化的数学证明。7.1 抽屉原理Pigeonhole Principle严密证明强抽屉原理表述 若将m个物体放入n个抽屉中且m n则至少存在一个抽屉其中包含不少于ceil(m / n)个物体。在本题场景中的映射物体Pigeons数组nums中包含的元素总量为m n 1个。抽屉Pigeonholes数值的合法取值范围为[1, n]中的整数共有n个可能的取值类别即n个抽屉。证明过程假设数组中没有任何重复数字即每一个抽屉中最多只能放置 1 个物体每个数值在数组中最多出现 1 次。那么n个抽屉所能容纳的物体最大总量为n * 1 n个。然而数组中实际包含的物体总量为n 1个。由于n 1 n这与“所有抽屉容纳物体总数不超过 n”发生直接矛盾矛盾表明初始假设不成立。因此数组中至少存在一个数值其对应的抽屉中放置了 2 个或 2 个以上的物体即至少存在一个重复的整数。7.2 图论连通性与入度证明从图论角度存在性证明可以表述为给定一个包含n 1个节点的有向图节点编号为0, 1, ..., n。每个节点有且仅有一条出边因此图的总边数为n 1条。所有边的终点编号只能属于{1, 2, ..., n}因为1 nums[i] n即起点0的入度为0。根据图论基本定理所有节点的入度之和等于总边数即InDegree(0) InDegree(1) ... InDegree(n) n 1因为InDegree(0) 0所以剩余n个节点的入度之和为InDegree(1) InDegree(2) ... InDegree(n) n 1根据均值原理在n个正整数的加和为n 1的条件下不可能所有InDegree(i) (i 1)都小于等于 1。必须至少存在一个节点k1 k n使得InDegree(k) 2。入度大于等于 2 意味着至少有两个不同的下标指向节点k即存在nums[i] nums[j] ki ! j。这证明了重复数字的存在性。八、 工业级拓展与典型变体防坑指南8.1 与 LeetCode 142. 环形链表 II 的映射关系LeetCode 287 本质上是 LeetCode 142环形链表 II的隐式化变体。LeetCode 142输入为一个显式的链表数据结构ListNode指针跳转语法为node node.next。LeetCode 287输入为一个物理数组int[]指针跳转语法映射为index nums[index]。两者解决环入口定位的算法底层数学逻辑完全一致。8.2 边界条件与常见陷阱数值 0 的陷阱为什么题目限定数值范围是[1, n]而非[0, n-1]原理如果数值包含0例如nums[0] 0那么起点0会直接指向自己形成自环导致快慢指针在起点处直接相遇算法失效。正是因为数值从1开始才确保了起点0的入度必为 0构成了安全从环外接入的链条。多重复元素的覆盖题目说明“只有一个整数出现两次或多次”但即使有多个不同的重复整数Floyd 判圈算法依然有效。图中可能会形成多个独立的环或交织环算法将精准锁定从起点 0 出发所能触及的第一条路径上的环入口返回该环入口对应的重复数值。不能使用异或XOR算法有开发者会误用 LeetCode 136只出现一次的数字中的异或位运算逻辑。原因异或消消乐算法仅适用于“重复数字出现恰好 2 次其余数字出现恰好 1 次”的情形。本题中重复数字可能出现3 次、4 次甚至 n 次如[3, 3, 3, 3, 3]异或运算无法消除奇数次重复带来的干扰必须采用图论判圈法。