力扣-287.寻找重复数

题目链接

287.寻找重复数

class Solution {public int findDuplicate(int[] nums) {int low = nums[0];int fast = nums[nums[0]];//1.快慢指针找相遇点while (low != fast) {low = nums[low];fast = nums[nums[fast]];}//2.双指针找入环点int pre = 0;while (pre != low) {pre = nums[pre];low = nums[low];}return pre;}
}

小结：对nums数组建图，每个位置i连一条i → nums[i]的边。由于有且仅有唯一的重复数字target，因此target这个位置一定有起码两条指向它的边，因此整张图一定存在环，且我们要找到的target就是这个环的入口，那么整个问题就等价于142. 环形链表 II。