确定映射关系:数组下标 -> 数组值 有重复元素就意味着必然有两条不同起点的边映射到一个值上,即指向同一个点,因此就会产生环 [1,2,4,5,6,4,3]
index -> value
映射关系
形成了0->1->2->4->6->3->5->4->6->3的环形表
至此,问题转换为 142 题 环形链表。那么针对此题,快、慢指针该如何走呢。根据上述数组转链表的映射关系,可推出 142 题中慢指针走一步 slow = slow.next ==> 本题 slow = nums[slow] 142 题中快指针走两步 fast = fast.next.next ==> 本题 fast = nums[nums[fast]]
class Solution {
public int findDuplicate(int[] nums) {
//快慢指针索引位置
int slow=nums[0], fast=nums[nums[0]];
//找到相遇结点
while (nums[slow]!=nums[fast]){
slow=nums[slow];
fast=nums[nums[fast]];
}
//找到起始结点
fast=0;
while (slow!=fast){
slow=nums[slow];
fast=nums[fast];
}
return slow;
}
}