目的:减少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];
…
因为是连续的子数组,在这个情况下滑动窗口就十分符合
定义两个指针 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; }
长度为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; } }