Basic knowledge

Reference:
Summary of slider window algorithm for Leetcode question brushing
Sliding window project of labuladong
Sliding window force buckle summary

Sliding window is mainly used to deal with continuous problems. Generally, the characteristics of these topics can be summarized as: find the longest / shortest substring, subsequence, subarray that meet XXX conditions (generally, these conditions are what calculation results are satisfied, how many times they appear, do not contain repeated characters, contain XXX and other conditions).

It can be divided into the following types:

1. Fixed window size
2. The window size is not fixed, and the maximum value satisfying the condition is solved
3. The window size is not fixed, and the minimum value satisfying the condition is solved

Several variables and concepts need to be defined in the sliding window:

1. The left and right pointers at both ends of the window and the surrounding window. The left and right pointers move according to the conditions. Window is used to store the value between the left and right pointers. According to the conditions of the topic, data structures such as array, HashSet, HashMap and so on can be flexibly used as windows.
2. Record one or more local variables res in the current window, which can be average, maximum length, minimum length, etc., and update constantly according to the window shrinkage.
3. Record the ans of the final result. After each window update above, select the variables that will affect the result to update the result.
4. Determining the timing of window contraction is the most critical and requires classified discussion. The author has sorted out the following articles and hopes to understand them slowly, Leetcode algorithm summary - sliding window algorithm analysis,Summary of slider window algorithm for Leetcode question brushing,Summary of three types of sliding window topics + general template: continuous update , for ease of understanding, the template is given below.

Algorithm template

Abstract the following templates in combination with relevant topics. You need to pay attention to legal shrinkage or illegal shrinkage, legal shrinkage of internal capture results, and illegal shrinkage of external capture results. A series of actions of window right may be in front of or behind illegal or legal windows.

(1) Window length variable maximization

while/if window illegal - > internal left shrinkage, external update status capture results

Perceptual understanding: as soon as the window is illegal, all illegal elements in the window need to be removed. Window right should be used at the right time, possibly before or after the window's legal judgment. When you have the attribute of de duplication, you usually need to use window right in window judgment first.

   HashSet<Character> set=new HashSet<>();
   char[] str=s.toCharArray();
   int len=str.length;
   int left=0;
   int ans=0;
   //1. The right boundary does not slide out
   for(int right=0;right<len;right++){
   //2. Or window right application
   	//2. Illegal window, while/if shrink window left
       while(set.contains(str[right])){
           set.remove(str[left++]);
       }
       //3. Or the above has been used
       //3. Use window right
       set.add(str[right]);
       //4. Update status, while/if external capture
       int res=right-left+1;
       ans=Math.max(ans,res);
   }
   return ans;

(2) Window length variable minimum

while/if window is legal - > internal left shrinkage, internal update status capture results, and window right is generally used before internal status update.

Perceptual understanding is: as soon as there is a legal window that meets the conditions, optimize and shrink it

	 int sum=0;
	 int len=nums.length;
	 int left=0;
	 int ans=Integer.MAX_VALUE;
	 //1. The right boundary does not slide out
	 for(int right=0;right<len;right++){
	 	//2. Use window right
	     sum+=nums[right];
	     //3. Window is legal, while/if shrink window left
	     while(sum>=target){
	         int res=right-left+1;
	         //4. Update status, while/if internal capture
	         ans=Math.min(res,ans);
	         sum-=nums[left++];
	     }
	 }
	 return ans==Integer.MAX_VALUE?0:ans;

(3) Calculate extreme value with fixed window length

if window just - > internal left shrinkage, internal update status capture results

int left=0;
int len=nums.length;
double ans=Integer.MIN_VALUE;
double sum=0;
//1. right the right boundary does not slide out
for(int right=0;right<len;right++){
	//2. Use window right
    sum+=nums[right];
    //3. The window is just right, if the interior shrinks window left
    if(right-left+1==k){
    	//4. Update status, if internal capture
        double res=sum/k;
        ans=Math.max(ans,res);
        sum-=nums[left++];
    }
}
return ans;

Related topics

(1) Window length variable maximization

3. Longest substring without repeated characters

The window needs to have the attribute of de duplication. At the same time, the topic requires to find the largest substring. If the condition is not met, the window will shrink.
In two ways, HashSet and while are used to continuously remove duplicate elements:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> set=new HashSet<>();
        char[] str=s.toCharArray();
        int len=str.length;
        int left=0;
        int ans=0;
        for(int right=0;right<len;right++){
        	//Use the while condition to remove the repeated characters one by one
            while(set.contains(str[right])){
                set.remove(str[left++]);
            }
            // window right join after illegal judgment
            set.add(str[right]);
            int res=right-left+1;
            ans=Math.max(ans,res);
        }
        return ans;
    }
}

HashMap records are used. key is the character element, Value is the last position of the element, if condition judgment is repeated, and left jumps to the next position of the last position.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[]str=s.toCharArray();
        int len=str.length;
        int left=0;
        int ans=0;
        HashMap<Character,Integer> map=new HashMap<>();
        for(int right=0;right<len;right++){
            if(map.containsKey(str[right])){
                //To constantly update to the right, take the maximum value
                left=Math.max(left,map.get(str[right])+1);
            }
            map.put(str[right],right);
            int res=right-left+1;
            ans=Math.max(ans,res);
        }
        return ans;
    }
}

1695. Delete the maximum score of the sub array

The maximum value of the deleted sub array refers to the sum of the scores of the deleted array, and the deleted array is not repeated continuously. Therefore, the window needs to have the attribute of de duplication, and a local variable is needed to record the sum of windows.

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        int ans=0;
        HashSet<Integer> set=new HashSet<>();
        int len=nums.length;
        int left=0;
        int sum=0;
        for(int right=0;right<len;right++){
            while(set.contains(nums[right])){
                sum-=nums[left];
                set.remove(nums[left++]);
            }
            //window right join after illegal judgment
            set.add(nums[right]);
            sum+=nums[right];
            ans=Math.max(ans,sum);   
        }
        return ans;
    }
}

1208. Make strings equal as much as possible

The focus of this problem is that the maximum length of a continuous string that can be converted between two strings can be solved continuously through a sliding window.

class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int left=0;
        int right;
        int sum=0;
        int ans=0;
        int len=s.length();
        for(right=0;right<len;right++){
        	//window right join before illegal judgment
            sum+=Math.abs(s.charAt(right)-t.charAt(right));
            while(sum>maxCost){
                sum-=Math.abs(s.charAt(left)-t.charAt(left));
                left++;
            }
            int res=right-left+1;
            ans=Math.max(ans,res);
        }
        return ans;
    }
}

1004. Number of maximum continuous 1 III

Using the greedy idea, when encountering 0, first offset with the number of times of K, until k<0, then start to shrink left, and update the result outside the illegal judgment.

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left=0;
        int len=nums.length;
        int ans=0;
        for(int right=0;right<len;right++){
            //Use the right boundary first
            if(nums[right]==0) k--;
            //Illegal judgment
            while(k<0){
                if(nums[left++]==0) k++;
            }
            //Result update
            int res=right-left+1;
            ans=Math.max(ans,res);
        }
        return ans;
    }
}

(2) Window length variable minimum

209. Subarray with the smallest length
Sum needs to record the sum in the window, res needs to update the array length, and needs to shrink when the conditions are met.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum=0;
        int len=nums.length;
        int left=0;
        int ans=Integer.MAX_VALUE;
        for(int right=0;right<len;right++){
            // window right join before legal judgment
            sum+=nums[right];
            while(sum>=target){
                int res=right-left+1;
                ans=Math.min(res,ans);
                sum-=nums[left++];
            }
        }
        return ans==Integer.MAX_VALUE?0:ans;
    }
}

(3) Calculate extreme value with fixed window length

643. Maximum average number of subarrays I
The if condition determines the fixed window size. After this calculation, the left boundary will shrink.

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int left=0;
        int len=nums.length;
        double ans=Integer.MIN_VALUE;
        double sum=0;
        for(int right=0;right<len;right++){
        	//window right join before legal judgment
            sum+=nums[right];
            if(right-left+1==k){
                double res=sum/k;
                ans=Math.max(ans,res);
                sum-=nums[left++];
            }
        }
        return ans;
    }
}