Leetcode: array fast and slow pointer method

The fast and slow pointer method refers to the operation of arrays 、 Linked lists and strings use two pointers with the same starting point but different forward steps . Instead of using multiple loops to solve problems , The time complexity of the fast and slow pointer method is low , High execution efficiency . For the fast and slow pointer method, there are only two points that can be adjusted according to the topic ：

1. The starting point
2. Forward steps

The choice of the starting point position of the fast and slow pointer method is usually a if else Sentence to judge , And when the correct starting position is not reached , The forward steps of the two pointers will be the same . The way to realize the inconsistent movement of the forward steps of the fast and slow pointer is usually to take a for Loop to move the pointer , Pay attention to the problem of cross-border . here for There are two schemes for loop iteration ：

1. You can set the steps of the fast and slow pointer to be the same , And then if After the judgment is successful, adjust the number of steps ,
2. You can also just set the iteration of the fast pointer , Again if Set the iteration of slow pointer in , If the judgment fails, the slow pointer does not advance , So as to realize the adjustment of the two steps

After understanding the basic frame of speed pointer , That is, the value of the preceding double pointer is consistent , Use one more for The cycle moves the fast and slow pointer at the same time and the same number of steps before reaching the correct starting position , At the right starting point , Adjust the forward steps of the fast pointer to be greater than the slow pointer , In the future, we will be interested in a simple LeetCode Practice the topic .

Array element removal

Topic link ：27. Remove elements

Title Description

Give you an array nums And a value val, You need In situ Remove all values equal to val The elements of , And return the new length of the array after removal .

Don't use extra array space , You have to use only O(1) Additional space and In situ Modify input array .

The order of elements can be changed . You don't need to think about the elements in the array that follow the new length .

explain :

Why is the return value an integer , But the output answer is array ?

Please note that , The input array is based on 「 quote 」 By way of transmission , This means that modifying the input array in a function is visible to the caller .

You can imagine the internal operation as follows :

// nums  In order to “ quote ” By way of transmission . in other words , Do not make any copies of the arguments 
int len = removeElement(nums, val);

//  Modifying the input array in a function is visible to the caller .
//  Based on the length returned by your function ,  It prints out the array   Within this length   All elements of .
for (int i = 0; i < len; i++) {
    
    print(nums[i]);
}

Example ：

Example 1

Input ：nums = [3,2,2,3], val = 3
Output ：2, nums = [2,2]
explain ： Function should return the new length 2, also nums The first two elements in are 2. You don't need to think about the elements in the array that follow the new length . for example , The new length returned by the function is 2 , and nums = [2,2,3,3] or nums = [2,2,0,0], It will also be seen as the right answer .

Example Two ：

Input ：nums = [0,1,2,2,3,0,4,2], val = 2
Output ：5, nums = [0,1,4,0,3]
explain ： Function should return the new length 5, also nums The first five elements in are 0, 1, 3, 0, 4. Note that these five elements can be in any order . You don't need to think about the elements in the array that follow the new length .

Tips ：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

Topic analysis

Briefly introduce the topic , Enter an array and the target value , Delete the values that match the target value in the array . Because the array space is continuous , You can only move the elements forward one by one after deleting the target value , Finish deleting . If you don't use the fast and slow pointer method , Instead, use double layers for Cycle violent cycle deletion , The corresponding time complexity will be O(n²), Low execution efficiency , But it can still solve the problem . The idea of fast and slow pointer method is as follows ：

1. Define two pointer variables , Starting values are 0
2. Nested one for Loop to move the pointer , Set fast pointer iteration
3. Judge the starting point of the pointer ： If the non target value , The elements pointed to by the fast pointer and the slow pointer are exchanged
4. Complete array loop , Just return the slow pointer

The program code is as follows ：

class Solution {
    
    public int removeElement(int[] nums, int val) {
    
        int fastIndex = 0;
        int slowIndex;
        for (slowIndex = 0; fastIndex < nums.length; fastIndex++) {
    
            if (nums[fastIndex] != val) {
    
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}