Array -- seven array topics with double pointer technique

One 、 Fast and slow pointer skills

Force to buckle 26 topic 「 Remove duplicate items from an ordered array 」, Let you redo in an ordered array ：

To solve this problem efficiently, we need to use fast and slow pointer skills ：

Let's slow the pointer slow Walk in the back , Quick pointer fast Go ahead and find the way , Find a non repeating element and assign it to slow And let slow Take a step forward .

such , To ensure that nums[0..slow] Are non repeating elements , When fast Pointer traverses the entire array nums after ,nums[0..slow] After the entire array is de duplicated .

class Solution {
    
    public int removeDuplicates(int[] nums) {
    
        int len=nums.length;
        if(len<=1) return len;
        int slow=0,fast=1;
        while(fast<len){
    
            if(nums[fast]!=nums[slow]){
    
                nums[++slow]=nums[fast];
            }
            fast++;
        }
        return slow+1;
    }
}

Just expand it a little bit , Take a look at the power button 83 topic 「 Delete duplicate elements from the sort list 」, If I give you an ordered single chain list , How to remove heavy ？

In fact, as like as two peas, the weight is exactly the same , The only difference is that it turns an array assignment into an operation pointer , You look at the previous code ：

class Solution {
    
    public ListNode deleteDuplicates(ListNode head) {
    
        if(head==null) return head;
        ListNode slow=head,fast=head.next;
        while(fast!=null){
    
            if(slow.val!=fast.val){
    
                slow.next=fast;
                slow=slow.next;
            }
            fast=fast.next;
        }
        slow.next=null;
        return head;
    }
}

Some readers may ask , The repeated elements in the linked list have not been deleted , Let these nodes hang on the linked list , Is it suitable ？

This is about to explore the characteristics of different languages , image Java/Python This kind of language with garbage collection , Can help us automatically find and recycle these 「 In the air 」 Memory of linked list nodes , And like C++ There is no automatic garbage collection mechanism for such languages , We really need to manually release the memory of these nodes when we write code .

In addition to getting you in an ordered array / In the linked list , The title may also let you edit some elements of the array 「 Delete in place 」.

For example, Li Kou di 27 topic 「 Remove elements 」

If fast Encountered value is val The elements of , Then skip directly , Otherwise, it will be assigned to slow The pointer , And let slow Take a step forward .

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

Next, let's look at Li Kou di 283 topic 「 Move zero 」：

Let's put all of them together 0 Move to the last , It's like removing nums All in 0, Then assign the following elements to 0 that will do .

So we can reuse the previous question removeElement function ：

void moveZeroes(int[] nums) {
    
    //  Remove  nums  All in  0, Return without  0  Array length of 
    int p = removeElement(nums, 0);
    //  take  nums[p..]  The element of is assigned the value of  0
    for (; p < nums.length; p++) {
    
        nums[p] = 0;
    }
}

//  See code implementation above 
int removeElement(int[] nums, int val);

Come here , The problems of modifying the array in place are almost the same . Another big class of fast and slow pointers in arrays is 「 Sliding window algorithm 」.

The specific topic will not be repeated in this paper , Only the fast and slow pointer characteristics of sliding window algorithm are emphasized here ：

left Pointer after ,right The pointer is in front of , The middle part of the two pointers is 「 window 」, The algorithm expands and shrinks 「 window 」 To solve some problems .

Two 、 Common algorithms for left and right pointers

1、 Two points search
Another article Binary search framework details The details of binary search code are discussed in detail , Here is the simplest binary algorithm , It aims to highlight its double pointer characteristics ：

int binarySearch(int[] nums, int target) {
    
    //  One left and one right pointer are facing each other 
    int left = 0, right = nums.length - 1;
    while(left <= right) {
    
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

2、 Sum of two numbers
Force to buckle 167 topic 「 Sum of two numbers II」

As long as the array is in order , You should think of the double pointer technique . The solution of this problem is similar to binary search , By adjusting the left and right It can be adjusted sum Size ：

int[] twoSum(int[] nums, int target) {
    
    //  One left and one right pointer are facing each other 
    int left = 0, right = nums.length - 1;
    while (left < right) {
    
        int sum = nums[left] + nums[right];
        if (sum == target) {
    
            //  The index of the title requirements is from  1  At the beginning 
            return new int[]{
    left + 1, right + 1};
        } else if (sum < target) {
    
            left++; //  Give Way  sum  A little bigger 
        } else if (sum > target) {
    
            right--; //  Give Way  sum  Smaller one 
        }
    }
    return new int[]{
    -1, -1};
}

3、 Inversion array
General programming languages provide reverse function , In fact, the principle of this function is very simple , Force to buckle 344 topic 「 Reverse string 」 It's a similar demand , Let you reverse one char[] Character array of type , Let's just look at the code ：

void reverseString(char[] s) {
    
    //  One left and one right pointer are facing each other 
    int left = 0, right = s.length - 1;
    while (left < right) {
    
        //  In exchange for  s[left]  and  s[right]
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

4、 Palindrome string judgment

boolean isPalindrome(String s) {
    
    //  One left and one right pointer are facing each other 
    int left = 0, right = s.length() - 1;
    while (left < right) {
    
        if (s.charAt(left) != s.charAt(right)) {
    
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Then I'll raise the difficulty a little , Give you a string , Let you use the double pointer technique to find the longest palindrome string , Will you do it? ？

Force to buckle 5 topic 「 Longest text substring 」：

The difficulty in retrieving the string is , The length of the palindrome string may be Odd number It could be even numbers , The core of solving this problem is A double pointer technique that spreads from the center to both ends .

If the length of the palindrome string is odd , Then it has a central character ; If the length of the palindrome string is even , It can be considered to have two central characters . So we can implement such a function first ：

//  stay  s  Search in order to  s[l]  and  s[r]  The longest palindrome string at the center 
String palindrome(String s, int l, int r) {
    
    //  Prevent indexes from crossing boundaries 
    while (l >= 0 && r < s.length()
            && s.charAt(l) == s.charAt(r)) {
    
        //  Double pointer , To both sides 
        l--; r++;
    }
    //  Return to  s[l]  and  s[r]  The longest palindrome string at the center 
    return s.substring(l + 1, r);
}

such , If you enter the same l and r, It is equivalent to looking for a palindrome string with an odd length , If you enter adjacent l and r, It is equivalent to looking for a palindrome string with an even length .

String longestPalindrome(String s) {
    
    String res = "";
    for (int i = 0; i < s.length(); i++) {
    
        //  With  s[i]  The longest palindrome string at the center 
        String s1 = palindrome(s, i, i);
        //  With  s[i]  and  s[i+1]  The longest palindrome string at the center 
        String s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.length() > s1.length() ? res : s1;
        res = res.length() > s2.length() ? res : s2;
    }
    return res;
}