Leetcode find duplicates

The details of the questions are as follows ：

Be careful ： The title requires that the array cannot be modified , You can't just use O(1) Extra space .

Method 1 （ Used O(n) Space ）：

Define a map<int,int>p, Traversal array nums, When you encounter an element in the array, you can see p Whether the current element has appeared , If it does , Then return the current element directly . Otherwise, it will be p The element marked in has already appeared .

Method 2 （ no need O(n) Space , But the array is modified ）：

Because the array length is n+1, Then the range of array elements is [1,n]. So you can first subscript from the array to 0 Start traversing the elements of , Record nums[0] Value , Then jump to nums[0] Value as the element corresponding to the subscript , Determine whether the element is -1, If -1, shows nums[0] It has appeared , Go straight back to nums[0]. Otherwise, define a variable v Record nums[nums[0]] Value , Then change the current element to -1, And jump to v Element with subscript , And repeat the process .
Here is an example ：

The right way

Suppose the methods and examples in method 2 , Suppose you don't modify the elements of the array , Then the traversal order of the array is ：

4->2->3->2->3->2->3........

here , We can find out , The array will go into a ring [2->3]

We assume that , There are two pointers slow and fast,slow Every step the pointer takes ,fast The pointer takes two steps . hypothesis slow The pointer is gone n Step , that fast The pointer is gone 2n Step , here slow Pointers and fast The pointer meets in the ring . Suppose the number of steps from the beginning to the beginning of the ring is m, The circumference inside the ring is c.
So we can get slow The pointer went inside the ring n-m Step ,fast The pointer went inside the ring 2n-m,fast The pointer is in the loop slow The pointer has gone too far n Step . Two pointers can meet in a ring , that fast Pointer ratio slow The pointer went a few more circles , So there is n%c=0

At this point, we define a pointer finder Start from the beginning ,slow The pointer also starts from the current position , Until the two pointers meet , The place where they meet is the place at the beginning of the ring , That is, the number of repetitions we are looking for , Why? ？
When finder Go to No m Step by step , I went to the beginning of the ring . So at this time ！！！！slow The pointer went inside the ring n-m+m=n Step . because n%c=0, therefore ,slow The pointer also goes to the beginning of the ring . therefore finder Pointers and slow The pointer will meet at the beginning of the ring .

According to the idea above , We have the following code ：

in addition leetcode There are similar topics ：