1. Sliding window method

Example: 209. Minimum length subarray (find the smallest array satisfying > = target)

Idea: use two pointers (similar to fast and slow pointers). If you are not satisfied, move the r pointer to the right until you are satisfied. If you are satisfied, move the l pointer to the left until you are not satisfied.

Method 1: single cycle, moving only one pointer at a time, meeting the requirement of moving left, not right.

This method takes less time than method 2, but the amount of code is more, because the first element needs to be processed separately (otherwise, if the first element has met the requirements, the first loop will move the left pointer to the right one bit, resulting in the left pointer to the right of the right pointer).

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n=nums.size();
        if(n==0)return 0;
        int left=0,right=0,total=nums[0];
        int min_len=INT_MAX;
        if(total>=target)return 1;
        while(right<n){
            if(total<target && right<n-1){
                right++;
                total+=nums[right];
            }
            else if(total>=target){
                total-=nums[left];
                min_len=min_len<right-left+1?min_len:right-left+1;
                left+=1;
            }
            else break;
        }
        return min_len==INT_MAX?0:min_len;
    }
};

Method 2: loop nesting. The outer loop is only responsible for moving the right pointer. After the right pointer is moved to meet the conditions, use the inner loop to move the left pointer until it is not met.

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n=nums.size();
        if(n==0)return 0;
        int min_len=INT_MAX,left=0,right=0,total=0;
        while(right<n){
            total+=nums[right];
            while(total>=target){
                min_len=min(min_len,right-left+1);
                total-=nums[left];
                left++; 
            }
            right++;
        }
        return min_len==INT_MAX?0:min_len;

    }
};

2. Double finger acupuncture

1. In the same direction

Example: 27. Remove elements( In situ Remove all elements equal to val in the array and return the new length of the array after removal.)

Idea: the fast pointer is responsible for traversal, and the slow pointer is responsible for storing new arrays.

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int black=0;
        int i;
        for(i=0;i<nums.size();i++){
            if(nums[i]==val) black+=1;
            else{
                nums[i-black]=nums[i];
            }
        }
        return i-black;
    }
};

2. Reverse

Example: 977. Square of ordered array (the integer array nums sorted in non decreasing order returns a new array composed of the square of each number. It is also required to be sorted in non decreasing order)

Idea: the left and right pointers are responsible for comparing the squares of the endpoints on both sides and constantly finding the largest square. The pointer can also move from the middle boundary to both sides, and is responsible for finding the minimum square, which will find the boundary point one step more.

Note: we should consider the case that the left (right) pointer moves to the bottom. For this problem, we should consider the case that there are only negative (positive) numbers.

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n=nums.size(),tem;
        vector<int> result(n,0);
        int left=0,right=n-1,site=n-1;
        for(int i=0;i<n;i++){
            nums[i]=nums[i]*nums[i];
        }
        while(left<=right){ 
            if(nums[left]>nums[right]){
                result[site--]=nums[left++];
            }
            else {
                result[site--]=nums[right--];
            }
        }
        return result;
    }
};

3. One knows two

If you want to operate two arrays together, you can think about whether you can have the operation result of one array and deduce the operation result of another array. If you can and don't bother, you can convert the problem of two arrays into the problem of one array.

for example 4. Find the median of two positive arrays

Using the idea of division, the focus is to find a division that makes:

1. The left of the split line in num1 < the right of the split line in num2;
2. The split line in num2 is left < the split line in num1 is right.

Since the lengths of the two arrays are known and the median is the first, we can know that as long as the position of the dividing line of one array is determined, the position of the dividing line of the other array can be calculated. Therefore, only consider moving the split line in an array, and determine whether the split line is left or right by binary search. The position of the split line in another array is calculated according to the position of the former.