滑动窗口Java_滑动窗口算法java

 

目录

思路：

总结

模板

 例题

---

当你看到最长，最短，xxx次数，包含xxx字符串等类似问题都可以想到滑动窗口来解答

思路：

当求最大路径时

1、首先，Max为0，右指针向右滑动，找到一个红球，然后因为找最优解,继续向右，然后遇到一个白球，此时就不是连续红球了，所以左窗口要进行收缩，向左两步；

 2、然后右窗口继续向右滑动直至有了白球，有了白球后，左窗口向右收缩

 3、然后右窗口向右滑动，又是一个白球，所以左窗口进行收缩；

 4、最后右窗口继续向右找到了四个红球，然后向右看还有没有更优解，结果遇到白球，

 5、此时左窗口向右进行收缩.....

直至右窗口遍历完毕，到达最后位置；

注意：每次右滑动记得最优值 

---

当求最短时（更靠近target）：

1.右指针先走，知道找到满足条件的地方，记录值

2、为了最优解，然后左指针向右收缩，看有没有更短的；

3、当左指针收缩，出现小于target时，右指针向右走看直至>=target

4、右指针导致value>target时，左指针收缩；

在数组末尾时结束 

总结

模板

 例题

 

package 滑动窗口;
 
/**
 * @author diao 2022/3/19
 */
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<nums.length){
            cur_sum+=nums[right];
 
            //3.如果cur_sum>=target，需要while遍历，将左指针往右收缩并记录最短路径
            while(cur_sum>=target){
 
                //3.1因为值已经>=target，所以我们要记录最小路径
                if(right-left+1<minLength||minLength==0){
                    minLength=right-left+1;
                }
 
                //因为left收缩，所以当前值cur_sum-nums[left]
                cur_sum=cur_sum-nums[left];
                //3.2左指针不断收缩，直至当前值小于target
                left++;
            }
            right++;
        }
        return minLength;
    }
}