灵神算法题单——滑动窗口（求子数组个数）

2799. 统计完全子数组的数目

class Solution {
public:int countCompleteSubarrays(vector<int>& nums) {int ant=0;int n=nums.size();unordered_map<int,int> m,mchild;for(int i=0;i<n;i++){m[nums[i]]++;}int mapnum=m.size();for(int i=0,j=0;i<n;i++){mchild[nums[i]]++;while(mchild.size()==mapnum){if(--mchild[nums[j]]==0)mchild.erase(nums[j]);j++;}ant+=j;}return ant;}
};

713. 乘积小于 K 的子数组

class Solution {
public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {int ant=0;int multi=1;int n=nums.size();for(int i=0,j=0;i<n;i++){multi*=nums[i];while(multi>=k&&j<=i){multi/=nums[j];j++;}ant+=i-j+1;}return ant;}
};

1358. 包含所有三种字符的子字符串数目

class Solution {
public:int numberOfSubstrings(string s) {int a[5];int ant=0;int n=s.size();for(int i=0,j=0;i<n;i++){a[s[i]-'a']++;while(a[0]&&a[1]&&a[2]){a[s[j]-'a']--;j++;}ant+=j;}return ant;}
};

2926.统计最大元素至少出现K次的子数组

     

class Solution {
public:long long countSubarrays(vector<int>& nums, int k) {long long ant=0;int s=0;int n=nums.size();int ma=ranges::max(nums);for(int i=0,j=0;i<n;i++){if(nums[i]==ma)s++;while(s==k){if(nums[j]==ma)s--;j++;}ant+=j;}return ant;}
};

2302.统计得分小于K 的子数组数目

class Solution {
public:long long countSubarrays(vector<int>& nums, long long k) {long long ant=0;int n=nums.size();long long t=0;for(int i=0,j=0;i<n;i++){t+=nums[i];while(t*(i-j+1)>=k){t-=nums[j];j++;}ant+=i-j+1;}return ant;}
};

2537. 统计好子数组的数目

class Solution {
public:long long countGood(vector<int>& nums, int k) {long long ant=0;unordered_map<int,int> m;int n=nums.size();long long t=0;for(int i=0,j=0;i<n;i++){t+=m[nums[i]]++;while(t>=k){t-=--m[nums[j]];j++;}ant+=j;}return ant;}
};

 2763.不间断子数组

class Solution {
public:long long continuousSubarrays(vector<int>& nums) {long long ant=0;int n=nums.size();multiset<int> s;for(int i=0,j=0;i<n;i++){s.insert(nums[i]);while(*s.rbegin()-*s.begin()>2){s.erase(s.find(nums[j++]));}ant+=i-j+1;}return ant;}
};