本文主要是介绍滑动窗口系列(不定长滑动窗口长度)9/4，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求子数组个数
一、乘积小于k的子数组
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
输入：nums = [10,5,2,6], k = 100 输出：8 解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
思路：
使用滑动窗口的思路，当右边界增大后，仍然满足条件的时候，此时增加的有效答案有：right-left+1.为什么呢？新增一个元素后，该元素和之前其他元素可以组成新的子数组，自己也可以作为子数组，所以有(right-left+1)个。
什么时候更新答案呢？当找到合适的left之后。
因为当更新右边界后，可能该滑动窗口不是满足条件的，所以在更新左边界之后，再计算有效的子数组。
代码：
class Solution {public int numSubarrayProductLessThanK(int[] nums, int k) {if(k<=1)return 0;int left=0;int right=0;int count=0;int multi=1;while(right<nums.length){multi*=nums[right];while(multi>=k){multi=multi/nums[left];left++;}if(multi<k)count+=right-left+1;right++;}return count;}
}二、包含所有三种字符的子字符串数目
给你一个字符串 s ，它只包含三种字符 a, b 和 c 。
请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。
输入：s = "abcabc" 输出：10 解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。
思路：
滑动窗口，只要找到第一个满足要求的子字符串，那么后面无论再加上什么，都是符合要求的。所以符合条件的字符串有s.length()-right;
那我们只需要找到满足要求的字符串，然后res+=s.length()-right;
while(count[0]>=1&&count[1]>=1&&count[2]>=1){res+=s.length()-right;count[s.charAt(left)-'a']--;left++;}代码：
class Solution {public int numberOfSubstrings(String s) {int[] count=new int[3];int left=0;int right=0;int res=0;while(right<s.length()){count[s.charAt(right)-'a']++;while(count[0]>=1&&count[1]>=1&&count[2]>=1){res+=s.length()-right;count[s.charAt(left)-'a']--;left++;}right++;}return res;}
}三、模型（当题目中要求 出现xxx 至少xx次)
思路：
这种题我们首先要找到符合条件的滑动窗口，然后所有符合条件的结果就是 总长度-right
在寻找符合条件的滑动窗口的时候，用while。
class Solution {public int countKConstraintSubstrings(String s, int k) {int[] arr=new int[2];int left=0;int right=0;int count=0;while(right<s.length()){//积累条件xxx//只要满足题目中的条件 就可以加了while(题目中给定的条件){count+=s.length()-right;arr[s.charAt(left)-'0']--;left++;}right++;}return xxx}
}四、统计完全子数组的数目
给你一个由 正 整数组成的数组 nums 。如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：
- 子数组中 不同 元素的数目等于整个数组不同元素的数目。
返回数组中 完全子数组 的数目。子数组 是数组中的一个连续非空序列。
输入：nums = [1,3,1,2,2] 输出：4 解释：完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。
思路：
1.首先统计一下数组中数字的种类distinctCount以及数量。使用数组统计(因为题目中数字的大小是1-2000)
2.定义一个变量completeCount记录滑动窗口中数字的种类；定义一个数组统计滑动窗口中数字的数量
3.滑动窗口右边界停止扩大，开始收割结果的条件：completeCount==distinctCount (子数组中 不同 元素的数目等于整个数组不同元素的数目。)
然后开始收割:res+=nums.length-right; 然后左边界移动，移动的时候数量要改变，如果数量==0，种类也要改变。
代码：
class Solution {public int countCompleteSubarrays(int[] nums) {//1.统计字符的数量 以及 字符的种类int distinctCount =0;int[] count=new int[2001];for(int num:nums){count[num]++;if(count[num]==1)distinctCount++;}//2.int left=0;int right=0;int res=0;int completeCount=0;int[] window=new int[2001];while(right<nums.length){window[nums[right]]++;if(window[nums[right]]==1)completeCount++;//如果滑动窗口中的种类==总的种类while(completeCount==distinctCount){res+=nums.length-right;window[nums[left]]--;if(window[nums[left]]==0){completeCount--;}left++;}right++;}return res;}
}五、统计好子数组的数目
给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。
一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。子数组 是原数组中一段连续 非空 的元素序列。
思路：
子数组中至少有k对满足条件，那么他就是一个好子数组。
1.首先我们要统计滑动窗口中有多少对满足条件的(i,j);记为 typeCount;
if(map.get(nums[right])>=2)typeCount+=map.get(nums[right])-1;每新加一个相同的数字，它就可以和前面所有的组成一个符合条件的数对。
2.如果typeCount>=k，滑动窗口的右边界就固定住。res+=nums.length-right;（因为右边界如果满足，那么以后的也一定满足）。
3.然后改变左边界，首先改变在map哈希表中的数量，然后改变typeCount;
while(typeCount>=k){res+=nums.length-right;int num=nums[left];map.put(nums[left],map.get(nums[left])-1);typeCount-=map.get(nums[left]);left++;}代码：
class Solution {public long countGood(int[] nums, int k) {int typeCount=0;int left=0;int right=0;long res=0;Map<Integer,Integer> map=new HashMap<>();while(right<nums.length){map.put(nums[right],map.getOrDefault(nums[right],0)+1);if(map.get(nums[right])>=2)typeCount+=map.get(nums[right])-1;while(typeCount>=k){res+=nums.length-right;map.put(nums[left],map.get(nums[left])-1);typeCount-=map.get(nums[left]);left++;}right++;}return res;}
}这篇关于滑动窗口系列(不定长滑动窗口长度)9/4的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
