• This article was first published on:Algorithmic Customs Clearance Manual
  • Text code address (welcomePainted “Star” 和 “Fork”) :Github.com/itcharge/Le…

1. Introduction to dual Pointers

Two Pointers: Means that instead of using a single pointer to access an element, Two Pointers are used to achieve the desired result. If the two hands are in opposite directions, they are called “counterclockwise”. If two Pointers are in the same direction, they are called “fast or slow Pointers”. If two Pointers belong to different arrays/lists, they are called “split double Pointers”.

The time complexity of violent algorithm is O(n2)O(n^2)O(n2). Dual Pointers take advantage of the monotonicity of intervals, thus reducing the time complexity to O (n) O (n) O (n).

2. Colliding Pointers

Colliding pointer: two Pointers, left and right, point to the first and last element in a sequence, and then the left pointer increases and the right pointer decreases until the values of the two Pointers collide (left == right) or other special conditions are met.

2.1 Solving steps of the collision pointer

  • Use two Pointersleft.right.leftRefers to the first element of the sequence, namely:left = 0.rightRefers to the last element of the sequence, namely:right = len(nums) - 1.
  • Move the left and right Pointers towards each other in the loop body. When certain conditions are met, move the left pointer to the right.left += 1. When another condition is met, the right pointer is moved to the left,right -= 1.
  • Until the two hands collide (i.eleft == right), or other special conditions are met to break out of the loop body.

2.2 Collision pointer pseudocode template

left = 0 
right = len(nums) - 1

while left < right:
    ifMeet the special conditions required:returnThe value that matches the conditionelifCertain conditions1:
        left += 1
    elifCertain conditions2:
        right -= 1

returnNo or value foundCopy the code

2.3 Scope of application of collision Pointers

Colliding Pointers are commonly used to solve ordered arrays or strings:

  • The problem of finding a set of elements in an ordered array that satisfy certain constraints: binary search, sum of numbers, etc.
  • String reversal problem: reverse string, palindrome number, reverse binary and other problems.

Let’s take a concrete example of how to use colliding Pointers to solve a problem.

2.4 Sum of two numbers II – Enter an ordered array

2.4.1 Title Links

  • 167. Sum of two numbers II – Input ordered array – LeetCode

2.4.2 General idea of the topic

Given an ascending array of integers: numbers and a target value, target.

Find two numbers in the array whose sum equals target, and return the values of the two numbers in the array.

Note: Array subscripts are counted from 1.

2.4.3 Solution idea

If the sum of two numbers is equal to target, the time complexity is O(n^2), you can try it.

class Solution:
    def twoSum(self, numbers: List[int], target: int) - >List[int] :
        size = len(numbers)
        for i in range(size):
            for j in range(i + 1, size):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]
        return [-1, -1]
Copy the code

It turns out there are no unexpected timeouts. So we need to find ways to reduce time complexity.

Because arrays are ordered, we can consider using double Pointers to reduce time complexity. Specific practices are as follows:

  • Use two Pointersleft.right.leftPoint to the first element of the array with the smallest value,rightPoints to the largest element of the array value.
  • Determines the sum of the elements at two positions in relation to the target value.
    • Returns two element positions if the sum of the elements is equal to the target value.
    • If the element sum is greater than the target value, letrightMove left. Keep checking.
    • If the element sum is less than the target value, letleftMove to the right. Keep checking.
  • untilleft 和 rightMove to the same position to stop detection.
  • Returns if it is not found[1, 1].

2.4.4 code

class Solution:
    def twoSum(self, numbers: List[int], target: int) - >List[int] :
        left = 0
        right = len(numbers) - 1
        while left < right:
            total = numbers[left] + numbers[right]
            if total == target:
                return [left + 1, right + 1]
            elif total < target:
                left += 1
            else:
                right -= 1
        return [-1, -1]
Copy the code

2.5 Verifying palindrome strings

2.5.1 Topic Links

  • 125. Verify palindrome string – LeetCode

2.5.2 Main idea of the topic

Given a string s.

Requirements: Determine whether it is a palindrome string (only alphanumeric characters are considered in the string, and the case of the letters is ignored).

  • Palindrome string: A string read forward and backward the same.

2.5.3 Solution idea

Use the collision pointer to solve. The specific steps are as follows:

  • Use two Pointersleft.right.leftPoint to the beginning of the string,rightPoints to the end of the string.
  • Check whether the characters corresponding to the two Pointers are letters or numbers. throughleftMoves to the right,rightLeft-shift filters out characters other than letters and numbers.
  • And then determines[start]Whether ands[end]Equal (attention to case).
    • If it is equal, thenleftMoves to the right,rightMove to the left to proceed to the next filter and judgment.
    • If not, it is not a palindrome string and is returned directlyFalse.
  • If you encounterleft == right, the string is a palindrome string and returnsTrue.

2.5.4 code

class Solution:
    def isPalindrome(self, s: str) - >bool:
        left = 0
        right = len(s) - 1
        
        while left < right:
            if not s[left].isalnum():
                left += 1
                continue
            if not s[right].isalnum():
                right -= 1
                continue
            
            if s[left].lower() == s[right].lower():
                left += 1
                right -= 1
            else:
                return False
        return True
Copy the code

2.6 Containers that hold the most water

2.6.1 Topic Links

  • 11. Container with the most water – LeetCode

2.6.2 General idea of the topic

Given n non-negative integers A1, A2… ,ana_1,a_2, … ,a_na1,a2,… An, each number represents a point in the coordinates (I, AI)(I, a_i)(I,ai). Draw n vertical lines in coordinates, and the two endpoints of vertical line I are (I, AI)(I, a_i)(I, AI) and (I,0)(I,0)(I,0)(I,0).

Requirements: find two vertical lines so that they and the X-axis together form a container can hold the most water.

Example:

  • Input:,8,6,2,5,4,8,3,7 [1]
  • Output:49
  • Explanation: The vertical lines in the figure represent the input array,8,6,2,5,4,8,3,7 [1]. In this case, the maximum amount of water the container can hold (shown in blue) is49.

2.6.3 Solution Ideas

As you can see from the example, if the left and right lines are determined, the amount of water that can be held is determined by the height of the lower line * the distance between the two lines. So we should make the lower line as high as possible, so as to make the water area as large as possible.

It can be solved using two Pointers. Move the pointer position of the lower line to get different heights and areas, and finally get the largest area among them. Specific practices are as follows:

  • Use two Pointersleft.right.leftPoint to the beginning of the array,rightPoints to the end of the array.
  • To calculateleft 和 rightThe area value of the composition, while maintaining and updating the maximum area value.
  • judgeleft 和 rightThe height value of.
    • ifleftThe height of the pointing line is lower, thenleftMove the pointer to the right.
    • ifrightThe height of the pointing line is lower, thenrightThe pointer moves to the left.
  • If you encounterleft == right, jump out of the loop, and finally return the maximum area.

2.6.4 code

class Solution:
    def maxArea(self, height: List[int]) - >int:
        left = 0
        right = len(height) - 1
        ans = 0
        while left < right:
            area = min(height[left], height[right]) * (right-left)
            ans = max(ans, area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return ans
Copy the code

3. Fast and slow pointer

Fast and slow Pointers: Two Pointers traverse the sequence from the same side and move one step faster than the other. A pointer that moves fast is called a fast pointer, and a pointer that moves slowly is called a slow pointer. The two Pointers move at different speeds and with different strategies until the fast pointer moves to the end of the array, or the two Pointers intersect, or some other special condition is met.

3.1 Solving steps of fast and slow Pointers

  • Use two Pointersslow,fast.slowGenerally refers to the first element of the sequence, namely:slow = 0.fastGenerally refers to the second element of the sequence, namely:fast = 1.
  • Moves the left and right Pointers to the right in the body of the loop. When certain conditions are met, move the slow pointer right, i.eslow += 1. When other conditions are met (or need not be met), move the fast pointer to the right, i.efast += 1.
  • Until the fast pointer moves to the end of the array (i.efast == len(nums) - 1), or two Pointers intersect, or jump out of the loop when other special conditions are met.

3.2 Fast and slow pointer pseudocode template

slow = 0
fast = 1
whileNot traversing:ifMeet the required special conditions: slow +=1
    fast += 1
returnThe appropriate valueCopy the code

3.3 Scope of application of fast and slow Pointers

Fast and slow Pointers are generally used to deal with moving and deleting elements in an array, or to determine whether there are rings or lengths in a linked list. The double pointer method for linked lists will be explained in detail in the linked list section.

Here’s how to use fast and slow Pointers to solve a problem.

3.4 Deleting duplicates from an ordered array

3.4.1 Topic Links

  • 26. Delete duplicates from ordered arrays – LeetCode

3.4.2 General idea of the topic

Given an ordered array nums.

Requirement: Remove duplicate elements from array NUMS so that each element appears only once. And prints the length of the array after removing the duplicate elements.

Note: You cannot use extra array space, modify the array in place and do so with O(1)O(1)O(1) extra space.

3.4.3 Solution idea

Because arrays are ordered, repeated elements must be adjacent.

Removing duplicate elements essentially moves the non-duplicate elements to the left of the array. Consider using double Pointers. The specific algorithm is as follows:

  1. Define two fast and slow Pointersslow.fast. Among themslowPoints to the end of the array after removing duplicate elements.fastPoints to the current element.
  2. makeslowIn the back,fastIn the former. makeslow = 0.fast = 1.
  3. To compareslowAnd the values of the elements at positionfastWhether the values of the elements in the position are equal.
    • If they are not equal, thenslowI’m going to move back one placefastThe element pointing to the position is copied toslowPosition.
  4. willfastMoves to the right1position
  • Repeat 3 to 4 steps untilfastEquals the length of the array.
  • returnslow + 1Is the length of the new array.

3.4.4 code

class Solution:
    def removeDuplicates(self, nums: List[int]) - >int:
        if len(nums) <= 1:
            return len(nums)
        
        slow, fast = 0.1

        while (fast < len(nums)):
            ifnums[slow] ! = nums[fast]: slow +=1
                nums[slow] = nums[fast]
            fast += 1
            
        return slow + 1
Copy the code

4. Separate dual Pointers

Split double Pointers: Two Pointers belong to different arrays/lists and move between two arrays/lists.

4.1 Separate the two-pointer solution steps

  • Use two Pointersleft_1,left_2.left_1Refers to the first element of the first array/list, that is:left_1 = 0.left_2Refers to the first element of the second array/list, that is:left_2 = 0.
  • When certain conditions are met, both Pointers move right at the same time, i.eleft_1 += 1,left_2 += 1.
  • When other certain conditions are met, willleft_1The pointer moves to the right, i.eleft_1 += 1.
  • When other certain conditions are met, willleft_2The pointer moves to the right, i.eleft_2 += 1.
  • It breaks out of the loop when one of the arrays/lists is iterated or when other special conditions are met.

4.2 Separating two-pointer pseudocode templates

left_1 = 0
left_2 = 0

while left_1 < len(nums1) and left_2 < len(nums2):
    ifCertain conditions1:
        left_1 += 1
        left_2 += 2
    elifCertain conditions2:
        left_1 += 1
    elifCertain conditions3:
        left_2 += 1
Copy the code

4.3 Separating the use range of double Pointers

Separating double Pointers is generally used to deal with ordered array combination, intersection and union problems. Here is a concrete example of how to use split double Pointers to solve the problem.

4.4 Intersection of two arrays

4.4.1 Topic Links

  • 349. Intersection of two arrays – LeetCode

4.4.2 General idea of the topic

Given two arrays nums1, nums2.

Requirement: Write a function to calculate their intersection. Repeat elements are counted only once.

4.4.3 Solution idea

Use the separated double pointer to solve, and the specific steps are as follows:

  • An arraynums1,nums2First order.
  • Use two Pointersleft_1,left_2.left_1Pointer to the first element of the first array, that is:left_1 = 0.left_2Pointer to the first element of the second array, that is:left_2 = 0.
  • ifnums1[left_1]Is equal to thenums2[left_2], add it to the answer array (note the de-duplication), and place theleft_1 和 left_2Moves to the right.
  • ifnums1[left_1]Less thannums2[left_2], it willleft_1Moves to the right.
  • ifnums1[left_1]Is greater thannums2[left_2], it willleft_2Moves to the right.
  • Finally, print an array of answers.

4.4.4 code

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) - >List[int] :
        nums1.sort()
        nums2.sort()

        left_1 = 0
        left_2 = 0
        res = []
        while left_1 < len(nums1) and left_2 < len(nums2):
            if nums1[left_1] == nums2[left_2]:
                if nums1[left_1] not in res:
                    res.append(nums1[left_1])
                left_1 += 1
                left_2 += 1
            elif nums1[left_1] < nums2[left_2]:
                left_1 += 1
            elif nums1[left_1] > nums2[left_2]:
                left_2 += 1
        return res
Copy the code

5. Two-pointer summary

Dual Pointers are divided into “colliding Pointers”, “fast and slow Pointers” and “separate dual Pointers”.

  • Colliding pointer: Two Pointers in opposite directions. It is suitable for solving the problem of finding a group of elements satisfying some constraints in an ordered array and the problem of string inversion.
  • Fast pointer: Two Pointers have the same direction. Suitable for solving the problems of moving and deleting elements in an array, or determining whether there are rings and lengths in a linked list.
  • Split double Pointers: Two Pointers belong to different arrays/lists. It is suitable for solving ordered array combination, intersection and union problems.

The resources

  • Fast and Slow Pointers for Dual-pointer Algorithms
  • [Blog post] Summary of all kinds of basic problems of dual-pointer algorithm – Digging gold
  • [Blog] Double pointer – force buckle plus – try to do the best algorithm in xihu District
  • 【 Blog 】LeetCode classification topic (4) — Dual pointer and sliding window 1 – Iwehdio – Expo Park
  • [Blog post] Summary of all kinds of basic problems of dual-pointer algorithm – Digging gold