sliding window

Basic concepts

Sliding window is an idea based on double pointers , A window is formed between the elements pointed to by the two pointers .

Application scenarios

About the problem
1、 Generally, the data structure given is an array or a string
2、 When finding the longest and shortest value of a substring or subsequence, or finding a target value
3、 The problem itself can be solved by violence
keyword
Satisfy XXX Conditions （ The result of the calculation is , Number of occurrences , Also include ）
The shortest / The longest
Substring / Subarray / Subsequence
for example ： Subarray with the smallest length

Slide window idea

Find the longest
—— The core ： Left and right hands （L,R） At the starting point ,R Slide the cycle bit by bit to the right
—— During each slide
If ： The elements in the window meet the conditions ,R Expand the window to the right , And update the optimal results
If ： The elements in the window do not meet the conditions ,L Narrow the window to the right
——R To the end

Find the shortest
—— The core ： Left and right hands （L,R） At the starting point ,R Slide the cycle bit by bit to the right
—— During each slide
If ： The elements in the window meet the conditions ,L Narrow the window to the right , And update the optimal results
If ： The elements in the window do not meet the conditions ,R Expand the window to the right
——R To the end

The code template

Longest template

// Longest template 
 initialization left,right,result,bestResult
while( The right pointer does not reach the end ){
    
	 The window expands , Join in right The corresponding element , Update current result
	while(result Not meeting the requirements ){
    
  		 The window shrinks , remove left The corresponding element ,left Move right 
  }
   Update the best results bestResult
  right++;
}
 return bestResult

Shortest template

// Shortest template 
 initialization left,right,result,bestResult
while( The right pointer does not reach the end ){
    
	 The window expands , Join in right The corresponding element , Update current result
	while(result Meet the requirements ){
    
		 Update the best results bestResult
  		 The window shrinks , remove left The corresponding element ,left Move right 
  }
  right++;
}
 return bestResult

leetcode Example

Given a containing n An array of positive integers and a positive integer target .

Find the sum of the array ≥ target The smallest length of Continuous subarray [numsl, numsl+1, …, numsr-1, numsr] , And return its length . If there is no sub array that meets the conditions , return 0 .
link ：https://leetcode.cn/problems/minimum-size-subarray-sum

Example 1：
Input ：target = 7, nums = [2,3,1,2,4,3]
Output ：2
explain ： Subarray [4,3] Is the smallest subarray in this condition .

Example 2：
Input ：target = 4, nums = [1,4,4]
Output ：1

Example 3：
Input ：target = 11, nums = [1,1,1,1,1,1,1,1]
Output ：0

Tips ：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

class Solution {
    
    public int minSubArrayLen(int target, int[] nums) {
    
           int left=0,right=0,minLength=0,sum=0;
            while (right<nums.length){
    
                sum=sum+nums[right];
                while (sum>=target){
    
                    if (right-left+1<minLength||minLength==0){
    
                        minLength=right-left+1;
                    }
                    sum=sum-nums[left];
                    left++;
                }
                right++;
            }
            return minLength;
    }
}

result ：