【LeetCode】十一、滑动窗口：长度最小的子数组 + 定长子串的元音最大数目

1、滑动窗口

如下，有一个数组，现三个元素为一组，求最大的和，自然可以while循环实现：i 、i+1、i+2三个相加，while条件是i+2 <= array.length，如此，前几次循环：

1 + 4 + 2
4 + 2 + 3
2 + 3 + 4

每次都有重复元素(前一次循环的后几位元素）被二次计算了，如三个一组时的i+1和i+2

如果现在不是三个一组，是三百万个一组，则这个重复计算的浪费太大，考虑使用滑动窗口：

依旧每次让i++前进一位，但结果不再重新累加，而是下一组的和 = 上一组的和 - 上一组的第一个元素 + 新框进来的元素。像窗口向前滑动，每次和上次相比，多了一个新元素，少了最开始的一个旧元素。

滑动窗口的应用场景如：数组中的定长问题，给定一个数组，指定长度K，求最大值或最小值。

2、leetcode209：长度最小的子数组

这题两个关键点：一是要求子数组是连续的，二是子数组不是定长的，但也可以用滑动窗口。

解决思路：开一个窗口，但这个窗口不是定长的，开始时，窗口左右两边界都为0，右边界右移，找到第一个子数组array，其和 >= s，然后记录长度。去掉array的第一个元素，如果其和仍然>=s，继续记录，接着再继续去掉array的第一个元素，直到不满足 >=s的条件时，窗口向前滑动，直到出现第二个子数组array

public class P209 {public static int getMinLength(int[] array, int s) {if (null == array || array.length == 0) {return 0;}// 默认值array.length + 1int result = array.length + 1;// 窗口的起始位置和结束位置int start = 0;int end = 0;// 窗口内元素的和int sum = 0;while (end < array.length) {sum = sum + array[end];// 找到了满足条件的子数组while (sum >= s) {// 窗口长度end - start + 1result = Math.min(result, end - start + 1);// 去掉窗口起始位置的元素sum = sum - array[start];// 窗口起始位置右移一位，看这个子数组能不能再缩减长度，以防出现 {1，1，1，999}这样的情况start++;}// 未找到子数组，或者子数组不能再缩减长度时，窗口结束位置右移一位，继续往下走end = end + 1;}// 如果result还等于默认值array.length + 1，则说明该值一直未被重新赋值，即全部元素加起来也不满足和>=s，返回0return result == array.length + 1 ? 0 : result;}
}

这题本质在求滑动窗口的最窄长度。

leetcode官方解释：

3、leetcode1456：定长子串中元音的最大数目

定长，考虑滑动窗口，先计算第一个k长度的窗口的元音数量，然后一步一步滑动到末尾，期间取Math.max()

public class P1456 {public static int getMaxNum(String s, int k) {if (null == s || s.length() == 0) {return 0;}HashSet set = new HashSet<String>();Collections.addAll(set, "a", "e", "i", "o", "u");int result = 0;int count = 0;String[] array = s.split("");// 先算出第一个窗口里元音的数量for (int i = 0; i < k; i++) {if (set.contains(array[i])) {count++;}}result = Math.max(result, count);// 窗口滑动int start = 0;int end = k - 1;while (end < array.length - 1) {// 滑出窗口的数据如果是元音，数量-1if (set.contains(array[start])) {count--;}// 滑进窗口的元素如果是元音，数量+1if (set.contains(array[end + 1])) {count++;}result = Math.max(result, count);// 本次窗口计算完成，向右滑动一步start++;end++;}return result;}
}

上面用了HashSet判断是否属于元音，也可用一下两种方法：

//纯方法
public int isVowel(char ch) {return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
}

//String对象的indexOf方法
String vowel = "aeiou";
vowel.indexOf('a');  //true