287. Looking for repeats - fast and slow pointer

287. Look for repetitions

Given an inclusion n + 1 Array of integers nums , The numbers are all in [1, n] Within the scope of （ Include 1 and n）, We know that there is at least one duplicate integer .

hypothesis nums Only A repeated integer , return The number of repetitions .

The solution you design must Don't modify Array nums And only constant level O(1) Extra space .

Example 1：

Input ：nums = [1,3,4,2,2]
Output ：2

Example 2：

Input ：nums = [3,1,3,4,2]
Output ：3

For this question
First , You can use the fast and slow pointer to find and change
If there is a change , Then the fast and slow pointers will meet in the ring , But the point of meeting , Not necessarily the starting point of change
Put the fast pointer back head, The speed pointer moves in the same step , Final , Will meet at the entrance of the ring
You blew the wind when I came , I returned to my hometown , Unexpectedly, we met again at the origin

int findDuplicate(int* nums, int numsSize) {
    
    int fast = 0;
    int slow = 0;
    while (true) {
    
        fast = nums[nums[fast]];
        slow = nums[slow];
        if (fast == slow) {
    
            fast = 0;
            while (fast != slow) {
    
                fast = nums[fast];
                slow = nums[slow];
            }
            return slow;
        }
    }
}