滑动窗口

基本概念

滑动窗口是一种基于双指针的一种思想，两个指针指向的元素之间形成一个窗口。

应用场景

有关问题
1、一般给出的数据结构是数组或者字符串
2、求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
3、该问题本身可以通过暴力求解
关键字
满足XXX条件（计算结果，出现次数，同时包含）
最短/最长
子串/子数组/子序列
例如：长度最小的子数组

滑动窗口思想

寻找最长
——核心：左右双指针（L,R）在起始点，R向右逐位滑动循环
——每次滑动过程中
如果：窗内元素满足条件，R向右扩大窗口，并更新最优结果
如果：窗内元素不满足条件，L向右缩小窗口
——R到达结尾

寻找最短
——核心：左右双指针（L,R）在起始点，R向右逐位滑动循环
——每次滑动过程中
如果：窗内元素满足条件，L向右缩小窗口，并更新最优结果
如果：窗内元素不满足条件，R向右扩大窗口
——R到达结尾

代码模板

最长模板

//最长模板
初始化left,right,result,bestResult
while(右指针没有到结尾){
    
	窗口扩大，加入right对应元素，更新当前result
	while(result不满足要求){
    
  		窗口缩小，移除left对应元素，left右移
  }
  更新最优结果bestResult
  right++;
}
返回bestResult

最短模板

//最短模板
初始化left,right,result,bestResult
while(右指针没有到结尾){
    
	窗口扩大，加入right对应元素，更新当前result
	while(result满足要求){
    
		更新最优结果bestResult
  		窗口缩小，移除left对应元素，left右移
  }
  right++;
}
返回bestResult

leetcode例题

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
链接：https://leetcode.cn/problems/minimum-size-subarray-sum

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：
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;
    }
}

结果：