技巧

寻找重复数

中等#287Java时间 O(n)空间 O(1)

题目要做什么

长度为 n+1 的数组中,每个元素都在 1 到 n 之间,只有一个数重复。不能修改数组,使用常数额外空间找出重复值。

题目示例输入nums = [1,3,4,2,2]
题目示例输出2

01 为什么这样做

把下标看作节点,nums[i] 看作下一节点。重复值使这条路径形成环。快慢指针先相遇,再让一个指针回到起点,两者同速前进时在环入口相遇。

始终成立的条件

第一阶段快指针每次走两步,慢指针走一步;第二阶段两者同速,入口即重复值。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public int findDuplicate(int[] nums) {3        int slow = 0, fast = 0;4        do {5            slow = nums[slow];6            fast = nums[nums[fast]];7        } while (slow != fast);8        int finder = 0;9        while (finder != slow) {10            finder = nums[finder];11            slow = nums[slow];12        }13        return finder;14    }15}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索