当前位置：首页 > news >正文

100.寻找重复数

news 2026/5/11 21:32:09

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

代码整体逻辑（先理解核心思想）

把数组抽象成一个带环的链表：数组的索引对应链表节点，nums[i] 对应节点 i 的下一个节点。

因为数组有重复数，必然会出现「多个索引指向同一个值」的情况，这就形成了环。
重复数就是「环的入口节点」，找到这个入口就能找到重复数。

算法分两步：

找快慢指针的相遇点：快指针（一次走两步）和慢指针（一次走一步）最终会在环内相遇。
找环的入口点：将其中一个指针重置到起点，两个指针以相同速度走，相遇处就是环的入口（即重复数）。

class Solution {public int findDuplicate(int[] nums) {// 初始化快慢指针，都指向起点（索引0）int slow = 0;int fast = 0;// 第一步：让快慢指针先各走一次（避免初始值相等直接跳过循环）slow = nums[slow];       // 慢指针走1步：从0 → nums[0]fast = nums[nums[fast]]; // 快指针走2步：从0 → nums[0] → nums[nums[0]]// 循环移动指针，直到快慢指针相遇（相遇在环内某个位置）while(slow != fast){slow = nums[slow];       // 慢指针每次走1步fast = nums[nums[fast]]; // 快指针每次走2步
        }// 第二步：找环的入口（重复数）int pre1 = 0;          // pre1 重置到起点（索引0）int pre2 = slow;       // pre2 留在快慢指针的相遇点// 两个指针以相同速度（每次走1步）移动，直到相遇while(pre1 != pre2){pre1 = nums[pre1]; // pre1 走1步pre2 = nums[pre2]; // pre2 走1步
        }// 相遇点就是环的入口，即重复数return pre1;}
}