Play with double pointer

One 、 Algorithm interpretation

Double pointers are mainly used to traverse arrays , Two pointers point to different elements , In order to accomplish the task together . It can also be extended to multiple pointers of multiple arrays .

If two pointers point to the same array , Traversal direction is the same and will not intersect , It is also called sliding window （ The area surrounded by two pointers is the current window ）, It is often used for interval search .

If two pointers point to the same array , But the traversal direction is opposite , It can be used to search , The array to be searched is often ordered .

Two 、 Sum of two numbers

2.1、 Sum of two numbers II - Input an ordered array

2.1.1、 Title Description

167. Sum of two numbers II - Input an ordered array

I'll give you a subscript from 1 The starting array of integers numbers , The array has been pressed Non decreasing order , Please find out from the array that the sum satisfying the addition is equal to the target number target Two numbers of . Let these two numbers be numbers[index1] and numbers[index2] , be 1 <= index1 < index2 <= numbers.length .

In length 2 Array of integers for [index1, index2] Returns the subscript of these two integers in the form of index1 and index2.

You can assume that each input Only corresponding to the only answer , And you Can not be Reuse the same elements .

The solution you design must use only constant level extra space .

2.1.2、 I / O example

Example 1：
Input ： numbers = [2, 7, 11, 15], target = 9
Output ： [1, 2]
explain ： 2 And 7 The sum is equal to the number of targets 9 . therefore index1 = 1, index2 = 2 . return [1, 2] .

Example 2：
Input ： numbers = [2, 3, 4], target = 6
Output ： [1, 3]
explain ： 2 And 4 The sum is equal to the number of targets 6 . therefore index1 = 1, index2 = 3 . return [1, 3] .

Example 3：
Input ： numbers = [-1, 0], target = -1
Output ： [1, 2]
explain ： -1 And 0 The sum is equal to the number of targets -1 . therefore index1 = 1, index2 = 2 . return [1, 2] .

2.1.3、 Answer key

3、 ... and 、 Array merge

3.1、 Merge two ordered arrays

3.1.1、 Title Description

88. Merge two ordered arrays

Here are two buttons Non decreasing order Array of arranged integers nums1 and nums2, There are two other integers m and n , respectively nums1 and nums2 The number of elements in .

Would you please Merge nums2 To nums1 in , Make the merged array press Non decreasing order array .

Be careful ： Final , The merged array should not be returned by the function , It's stored in an array nums1 in . In response to this situation ,nums1 The initial length of is m + n, The top m Elements represent the elements that should be merged , after n Elements are 0 , It should be ignored .nums2 The length of is n .

3.1.2、 I / O example

Example 1：
Input ： nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
Output ： [1, 2, 2, 3, 5, 6]
explain ： Need merger [1, 2, 3] and [2, 5, 6] . The combined result is [1, 2, 2, 3, 5, 6] ,
     In which, bold italics indicates nums1 The elements in .

Example 2：
Input ： nums1 = [1], m = 1, nums2 = [], n = 0
Output ： [1]
explain ： Need merger [1] and [] .
     The combined result is [1] .

Example 3：
Input ： nums1 = [0], m = 0, nums2 = [1], n = 1
Output ： [1]
explain ： The array to be merged is [] and [1] .
     The combined result is [1] .
Be careful , because m = 0 , therefore nums1 No elements in .nums1 The only remaining 0 Just to ensure that the merged results can be successfully stored in nums1 in .

3.1.3、 Answer key

Four 、 Speed pointer

4.1、 Circular list II

4.1.1、 Title Description

142. Circular list II

Given the head node of a linked list head , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to null.

If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. If pos yes -1, There are no links in the list . Be careful ：pos Not passed as an argument , Just to identify the actual situation of the linked list .

No modification allowed Linked list .

4.1.2、 I / O example

Example 1：

Input ： head = [3, 2, 0, -4], pos = 1
Output ： The return index is 1 The linked list node of
explain ： There is a link in the list , Its tail is connected to the second node .

Example 2：

Input ： head = [1, 2], pos = 0
Output ： The return index is 0 The linked list node of
explain ： There is a link in the list , Its tail is connected to the first node .

Example 3：

Input ： head = [1], pos = -1
Output ： return null
explain ： There are no links in the list .

4.1.3、 Answer key

5、 ... and 、 The sliding window

5.1、 Minimum cover substring

5.1.1、 Title Description

76. Minimum cover substring

Give you a string s 、 A string t . return s Covered by t The smallest string of all characters . If s There is no coverage in t Substring of all characters , Returns an empty string "" .

Be careful ：

• about t Duplicate characters in , The number of characters in the substring we are looking for must not be less than t The number of characters in the .
• If s There is such a substring in , We guarantee that it is the only answer .

5.1.2、 I / O example

Example 1：
Input ： s = “ADOBECODEBANC”, t = “ABC”
Output ： “BANC”

Example 2：
Input ： s = “a”, t = “a”
Output ： “a”

Example 3：
Input ： s = “a”, t = “aa”
Output ： “”
explain ： t Two characters in ‘a’ Shall be included in s In the string of ,
Therefore, there is no qualified substring , Returns an empty string .

5.1.3、 Answer key

6、 ... and 、 practice

6.1、 Basic difficulty

6.1.1、 Sum of squares

6.1.1.1、 Title Description

633. Sum of squares

Given a nonnegative integer c , You have to decide if there are two integers a and b, bring a2 + b2 = c .

6.1.1.2、 I / O example

Example 1：
Input ： c = 5
Output ： true
explain ： 1 * 1 + 2 * 2 = 5

Example 2：
Input ： c = 3
Output ： false

6.1.1.3、 Answer key

6.1.2、 Verify palindrome string Ⅱ

6.1.2.1、 Title Description

680. Verify palindrome string Ⅱ

Given a non empty string s, most Delete a character . Determine whether it can be a palindrome string .

6.1.2.2、 I / O example

Example 1：
Input ： s = “aba”
Output ： true

Example 2：
Input ： s = “abca”
Output ： true
explain ： You can delete c character .

Example 3：
Input ： s = “abc”
Output ： false

6.1.2.3、 Answer key

6.1.3、 Delete the longest letters from the dictionary

6.1.3.1、 Title Description

524. Delete the longest letters from the dictionary

Give you a string s And an array of strings dictionary , Find out and return to dictionary The longest string in , The string can be deleted s Some characters in get .

If there is more than one answer , Returns the string with the longest length and the smallest alphabetical order . If the answer doesn't exist , Returns an empty string .

6.1.3.2、 I / O example

Example 1：
Input ： s = “abpcplea”, dictionary = [“ale”, “apple”, “monkey”, “plea”]
Output ： “apple”

Example 2：
Input ： s = “abpcplea”, dictionary = [“a”, “b”, “c”]
Output ： “a”

6.1.3.3、 Answer key

6.2、 Advanced difficulty

6.2.1、 At most K Longest substring of different characters

6.2.1.1、 Title Description

340. At most K Longest substring of different characters

Given a string s , find at most contain k Longest substring of different characters T.

6.2.1.2、 I / O example

Example 1：
Input ： s = “eceba”, k = 2
Output ： 3
explain ： be T by “ece”, So the length is 3.

Example 2：
Input ： s = “aa”, k = 1
Output ： 2
explain ： be T by “aa”, So the length is 2.

6.2.1.3、 Answer key