Leetcode—287. 寻找重复数【中等】（快慢指针算法）

本文主要是介绍Leetcode—287. 寻找重复数【中等】（快慢指针算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024每日刷题（136）

Leetcode—287. 寻找重复数

在这里插入图片描述

快慢指针算法思想

low = fast 时，快慢指针相遇，low 走过的距离是初始点（0）到环状开始的点（x）加上环状开始的点（x）到相遇点（y）这段距离，而fast走过的距离是初始点（0）到环状开始的点（x），点（x）到点（y），点（y）到点（x），点（x）到点（y）。又因为fast走过的距离是low的两倍，设0到x长度为a，x到y长度为b,则有2*（a+b） = a+ b+ (y到x的距离) + b，则y到x的距离就等于0到x的距离。所以当新的两个指针一个从0出发，一个从相遇点y出发时，他们走到的相同的值就是环状开始的点，即x点。

在这里插入图片描述

实现代码

class Solution {
public:int findDuplicate(vector<int>& nums) {int slow = nums[nums[0]];int fast = nums[nums[nums[0]]];while(slow != fast) {slow = nums[slow];fast = nums[nums[fast]];}slow = nums[0];while(slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;}
};