算法学习——滑动窗口

本文主要是介绍算法学习——滑动窗口，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

滑动窗口

目的：减少while循环

标志：数组中定长问题（以k为长度，求最大(小)的和）、求连续的数

理解：每次这组数移动只需要加上新的数并减去末尾的数

例子：

1 3 5 7 8 5 4 3 5 7 int[] arr = {1,3,5,7,8,5,4,3,5,7}

长度k == 3;求没三个相邻数相加最大和；

第一次：sum == 1+3+5；arr[0]+arr[1]+arr[2];

第二次：sum + 7 -1; arr[0]+arr[1]+arr[2]+arr[3]-arr[0];

第三次：sum + 8 -3；arr[1]+arr[2]+arr[3]+arr[4]-arr[1];

…

力扣209 长度最小的子数组

因为是连续的子数组，在这个情况下滑动窗口就十分符合

定义两个指针 left 和 right，构成一个滑动窗口，当窗口内的数值和小于 s 时，右指针向右滑动，当窗口内的数值和大于等于 s 时，就要更新一次 子数组的最小长度了。同时 左指针向右滑动。

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int l = 0, r = -1; 
        int sum = 0;
        int res = nums.length + 1;
        while (l < nums.length) {   
        	// 窗口的左边界在数组范围内,则循环继续
            if (r + 1 < nums.length && sum < s) {
                sum += nums[++r];
            } else {
           	 	// r已经到头 或者 sum >= s
                sum -= nums[l++];
            }
            if (sum >= s) {
                res = Math.min(res, r - l + 1);
            }
        }
        if (res == nums.length + 1) {
            return 0;
        }
        return res;
    }

力扣1456 定长子串中元音的最大数目

长度为k的单个子字符串中可能包含的最大元音字母数

长度为k——滑动窗口。

第一步寻找元音。利用哈希set判断

第二部for循环判断第一个窗口，计数有几个元音

第三步开始滑动窗口，

当i<k，i<数组的长度时，

for循环判断上个窗口第一位（下标为i-k） 如果是元音计数减一

​ 最后一位（下标位i) 是不是元音 如果是元音计数加一

​ 比较之前的计数和本次循环的计数 取较大的 作为最大元音数

class Solution {
    public int maxVowels(String s, int k) {
    if(s==null || s=="" || s.length()<k)
    return 0;
    int maxSubLen=0;
    int num=0;//记元音个数
    Set set = new HashSet();
    set.add('a');
    set.add('e');
    set.add('i');
    set.add('o');
    set.add('u');
//先找第一个窗口
    for(int i=0;i<k;i++)
    {
        if(set.contains(s.charAt(i)))
        num++;
    }
    maxSubLen=Math.max(maxSubLen,num);
//向后滑动
    for(int i=k;i<s.length();i++)
    {
        //判断原头是否是元音
        if(set.contains(s.charAt(i-k)))
        num--;
        //判断当前尾是否是元音
        if(set.contains(s.charAt(i)))
        num++;
        maxSubLen=Math.max(maxSubLen,num);
    }
    return maxSubLen==0?0:maxSubLen;
    }
}

这篇关于算法学习——滑动窗口的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！