滑动窗口系列(定长滑动窗口长度)8/31

1.长度为K子数组中的最大和

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

子数组的长度是 k，且
子数组中的所有元素 各不相同

题意：

在之前题目的基础上添加了一个条件：子数组中的所有元素各不相同。

因此在这里使用哈希表记录元素出现的次数

思路：

在循环中

1.首先要判断该数字之前是否出现过? 如果出现过，就要将滑动窗口的左边界移动到该数字的下一个。

            while (map.getOrDefault(nums[right], 0) != 0) {map.put(nums[left], map.get(nums[left]) - 1);sum -= nums[left];left++;}

2.然后sum累计求和(第一步中判断了没有出现过才加的)，如果滑动窗口的长度==k，此时更新一下最大值，然后移动滑动窗口的左边界并且更新一下哈希表；

            sum += nums[right];map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);if (right - left + 1 == k) {max = Math.max(max, sum);sum -= nums[left];map.put(nums[left], map.get(nums[left]) - 1);left++;}

3.返回最大值

代码：

 class Solution {public long maximumSubarraySum(int[] nums, int k) {long max = 0;int left = 0;int right = 0;long sum = 0;Map<Integer, Integer> map = new HashMap<>();while (right < nums.length) {while (map.getOrDefault(nums[right], 0) != 0) {map.put(nums[left], map.get(nums[left]) - 1);sum -= nums[left];left++;}sum += nums[right];map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);if (right - left + 1 == k) {max = Math.max(max, sum);sum -= nums[left];map.put(nums[left], map.get(nums[left]) - 1);left++;}right++;}return max;}
}

2.爱生气的书店老板(有点绕）

题意：

有一个书店，开了n分钟,每一分钟会进x个人，用数组customers表示；这老板脾气有点大，每一分钟可能会生气,用数组grumpy表示；如果生气的话，顾客就会不满意；但是老板有一个秘诀，会抑制生气，只能抑制minutes分钟；求n分钟最多满意的顾客有多少人？

输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

思路：

1.首先假设不会抑制情绪，那么顾客数为最少的，人数记为basic；

   for(int i=0;i<customers.length;i++){if(grumpy[i]==0)basic+=customers[i];}

2.选择在何时抑制情绪，这里可以使用滑动窗口的思路；

2.1 遍历数组，如果该分钟老板是生气的,那么顾客数就要在basic的基础上增加

2.2 然后要判断滑动窗口的长度，如果==minutes,那么就要更新最大值，并且更新滑动窗口的边界

        while(right<customers.length){if(grumpy[right]==1)basic+=customers[right];if(right-left+1==minutes){max=Math.max(max,basic);if(grumpy[left]==1)basic-=customers[left];left++;}right++;}

代码：

class Solution {public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {int left=0;int right=0;int max=Integer.MIN_VALUE;int basic=0;for(int i=0;i<customers.length;i++){if(grumpy[i]==0)basic+=customers[i];}while(right<customers.length){if(grumpy[right]==1)basic+=customers[right];if(right-left+1==minutes){max=Math.max(max,basic);if(grumpy[left]==1)basic-=customers[left];left++;}right++;}return max;}
}

3.子串出现的最大次数()

题意：

给你一个字符串 s ，请你返回满足以下条件且出现次数最大的任意子串的出现次数：

子串中不同字母的数目必须小于等于 maxLetters 。
子串的长度必须大于等于 minSize 且小于等于 maxSize 。

输入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
输出：2
解释：子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。

思路：只需要看minSize就可以，因为长度为maxSize的字符串一定是覆盖长度为minSIze的字符串的；eg:bcdabcdabcdabc minSize=3 maxSize=4 abcd会出现3次，abcd出现abc一定出现;

因此这道题就变成了，滑动窗口长度为minSize,寻找不同字母的数量要<=maxLetters的字符串。这个字符串可能有多个，返回一个数量最多的。

代码：

class Solution {public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {int left=0;int right=0;int count=0;int max=0;Map<Character,Integer> map1=new HashMap<>();//记录滑动窗口中出现字母的次数Map<String,Integer> map2=new HashMap<>();//记录符合字符串出现的次数while(right<s.length()){char ch=s.charAt(right);if(map1.getOrDefault(ch,0)==0)count++;map1.put(ch,map1.getOrDefault(ch,0)+1);if(right-left+1==minSize){if(count<=maxLetters){String str=s.substring(left,right+1);map2.put(str,map2.getOrDefault(str,0)+1);max=Math.max(max,map2.get(str));}map1.put(s.charAt(left),map1.get(s.charAt(left))-1);if(map1.get(s.charAt(left))==0)count--;left++;}right++;}return max;}
}

4.最小交换次数来组合所有的1 II

题意：

交换定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。

环形数组是一个数组，可以认为 第一个 元素和 最后一个 元素相邻。

给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。

思路：

要组合所有的1，我们可以将滑动窗口的长度设置为1的个数；

如果滑动窗口中0的个数为0：就不需要交换，交换次数为0；

如果滑动窗口中0的个数为1：就需要将1和这个0交换，交换次数为1；

因此，0的个数就是需要交换的个数；

因此只需要使用滑动窗口判断里面0的个数即可。并且更新最小值；

注意：是循环数组

left和right的增加都需要对size取余

代码：

class Solution {public int minSwaps(int[] nums) {//计算窗口的长度(数组中1的个数就是窗口的长度)int windowSize=0;for(int num:nums)if(num==1)windowSize++;int left=0;int right=0;int res=Integer.MAX_VALUE;int count=0;int index=0;while(index<windowSize+nums.length-1){if(nums[right]==0)count++;if(right-left+1==windowSize||right+nums.length-left+1==windowSize){res=Math.min(res,count);if(nums[left]==0)count--;left=(left+1)%nums.length;}right=(right+1)%nums.length;index++;}return res==Integer.MAX_VALUE?0:res;}
}