求子数组个数
一、乘积小于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;
}
}