For example, if two Pointers are moving in the same direction at the same time, and if they are moving in the opposite direction at the same time, they are moving opposite to each other.

LeetCode is involved

The problem, Name of the problem The difficulty
167  Two Sum II – Input array is sorted easy
344 Reverse String easy
26 Remove Duplicates from Sorted Array easy

In general, many problems are related to arrays, which are the main object of most algorithms as a data structure.

synthetic

Two Pointers moving in the same direction are in the same direction.

interval describe
0 – i Processed data
i – j Processed, but not needed data
j – n Data to be processed

The definition of whether each interval is left closed and right open or some other form depends on the problem, it needs to be consistent, and the elements on the interval boundary cannot have both meanings.

reverse

The reverse is simpler than the same, i.e., 0 – I and j – n are processed data.

General steps for solving problems

  • Initialize the pointer to 2, 0 if it is from left to right, n otherwise
  • The next step is to move the j pointer forward to know the end of the array (list), and every time we move j forward to check if j is the value we want, if j is the value we want, we copy the value of j to I, and we move I forward one position to wait for the next value we want. If the j position is not what we need, we move forward to the next position.

In actual combat

Reverse String

This is a problem of flipping strings, writing a function that reverses strings. The input string is an array of characters s. String flips are implemented by adjusting the original array without opening new space.

For this problem we can use the template introduced above to apply this problem, in fact, this step is a more complicated step. When we get a question how to match it to a knowledge point, this is also the aspect that the interviewer wants to examine you, which is also difficult. Usually, we can read the question and are familiar with various algorithms, but we just don’t know how to put the algorithm into the seat.

class Solution:
    def reverseString(self, s: List[str]) - >None:
        """ Do not return anything, modify s in-place instead. """
        i = 0
        j = len(s) - 1
        while i < j:
            tmp = s[i]
            s[i] = s[j]
            s[j] = tmp
            i += 1
            j -= 1
Copy the code

So this is where we start and end our array and swap the I and j positions to reverse the string. The number of string characters can be even or odd for I

I’m going to illustrate this process in graphic form, and hopefully get you a thumbs up.

Two Sum II – Input array is sorted

We know that we have an array of integers sorted from smallest to largest, and we find two numbers that add up to a particular number. An array containing the corresponding index of two numbers, starting with the expression 1 instead of 0.

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

The problem is simple because this is an array from small to large, and then Pointers from left to right.

Remove Duplicates from Sorted Array

Given an array of integers, numS, ordered from smallest to largest, it is required to remove duplicate elements, that is, each element appears only once. When duplicate elements are removed, the relative positions of each element should remain the same, with the requirement that no additional space can be created.

Now that I’ve illustrated how to solve this problem in the same direction, let’s take a look at the code. Once we’ve analyzed the problem clearly, the code should not look too difficult.

class Solution:
    def removeDuplicates(self, nums: List[int]) - >int:
        print(len(nums))
        i = 0
        j = 0
        while j < len(nums):
            if i == 0 or(nums[j] ! = nums[i-1]):
                nums[i] = nums[j]
                i += 1
                j += 1
                
                
            else:
                j+=1
        
        return i
Copy the code