LeetCode 287. 寻找重复数

题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

思路

思路：这道题可以理解为环形链表II的数组版本。
根据题解287.寻找重复数，得到的一个重要结论是从理论上讲，数组中如果有重复的数，那么就会产生多对一的映射，这样，形成的链表就一定会有环路了
所以类似于链表一样，弄一个快慢指针，慢指针一次一步，快指针一次两步，找到链表的环，再通过环形链表II中的x=z，弄一个从起点出发的指针和一个从快慢指针交汇处出发的指针，来找到这个环的入口（也就是重复数）

代码

class Solution {public int findDuplicate(int[] nums) {// 找环int slow = 0;int fast = 0;slow = nums[slow];fast = nums[nums[fast]];while (slow != fast) {slow = nums[slow];fast = nums[nums[fast]];}// 找交汇点int pre1 = 0;int pre2 = slow;while (pre1 != pre2) {pre1 = nums[pre1];pre2 = nums[pre2];}return pre1;}
}