目录
思路:
总结
模板
例题
当你看到最长,最短,xxx次数,包含xxx字符串等类似问题都可以想到滑动窗口来解答
思路:
当求最大路径时
1、首先,Max为0,右指针向右滑动,找到一个红球,然后因为找最优解,继续向右,然后遇到一个白球,此时就不是连续红球了,所以左窗口要进行收缩,向左两步;
2、然后右窗口继续向右滑动直至有了白球,有了白球后,左窗口向右收缩
3、然后右窗口向右滑动,又是一个白球,所以左窗口进行收缩;
4、最后右窗口继续向右找到了四个红球,然后向右看还有没有更优解,结果遇到白球,
5、此时左窗口向右进行收缩.....
直至右窗口遍历完毕,到达最后位置;
注意:每次右滑动记得最优值
当求最短时(更靠近target):
1.右指针先走,知道找到满足条件的地方,记录值
2、为了最优解,然后左指针向右收缩,看有没有更短的;
3、当左指针收缩,出现小于target时,右指针向右走看直至>=target
4、右指针导致value>target时,左指针收缩;
在数组末尾时结束
总结
模板
例题
package 滑动窗口;
public class 寻找满足值的最小序列长度 {
public static void main(String[] args) {
int[] nums={1,2,3,4,5,6};
int i = find(nums, 5);
System.out.println(i);
}
public static int find(int nums[],int target){
//1.分析变量
int left=0;
int right=0;
int cur_sum=0;
int minLength=0;
//2.进行遍历,寻找最短路径
while(right=target,需要while遍历,将左指针往右收缩并记录最短路径
while(cur_sum>=target){
//3.1因为值已经>=target,所以我们要记录最小路径
if(right-left+1



