LeetCode 1248 统计优美子数组
🟡 中等 https://leetcode.cn/problems/count-number-of-nice-subarrays/description/
可以使用动态规划求解：
以 [2，2，2，1，2，2，1，2，2，2] ，限制2个1为例：
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
vector<int> pre(nums.size()+1,0);
int count = 0;
for(int i = nums.size()-1;i>=0;i--){
if(nums[i]%2==0){
pre[i] = pre[i+1];
count++;
}else{
pre[i]=count+1;
count=0;
}
}
for(int i = 2;i<=k;i++){
vector<int> current(nums.size()+1,0);
for(int j = nums.size()-1;j>=0;j--){
if(nums[j]%2==0){
current[j] = current[j+1];
}else{
current[j] = pre[j+1];
}
}
pre = current;
}
return accumulate(pre.begin(),pre.end(),0);
}
};
时间复杂度：O(n*k) ，超时了。
滑动窗口
在找到窗口内奇数个数为k时，设置tmp，假装滑动，我们要找到以i结尾的所有合法子数组的左边界，左边界可能时当前的left，也可能时右边第一个奇数。
使用tmp滑动到第一个奇数，所以while条件设置相反的，停在奇数后，求长度即可。
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int left = 0;
int res = 0;
int window_count = 0;
for(int i = 0;i<nums.size();i++){
if(nums[i]%2==1){
window_count++;
}
while(window_count>k){
if(nums[left]%2==1) window_count--;
left++;
}
if(window_count==k){
int tmp = left;
while(nums[tmp]%2==0){
tmp++;
}
res+=tmp-left+1;
}
}
return res;
}
};
其他
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
vector<int> odd_index;
odd_index.push_back(-1);
int pre_odd = 1;
int ans = 0;
for(int i = 0;i<=nums.size();i++){
if(i==nums.size()||nums[i]%2==1) odd_index.push_back(i);
if(odd_index.size()-1-pre_odd+1==k+1){
int left = odd_index[pre_odd]-odd_index[pre_odd-1];
int right = i-1-odd_index[odd_index.size()-2]+1;
ans +=left*right;
pre_odd++;
}
}
return ans;
}
};