求恰好为k 的区间数量（滑动窗口进阶版）

前言：之前做的滑动窗口都是可以直接一遍过，然后每次右边确定了以后，左边不断缩小寻找最优解

但是这个题目呢我们不仅要保证我们的辅音字母的个数恰好为k，其他元音字母的个数只要每个都出现了就行，这个就导致我们不能用正常的思路来考虑这个问题

我们可以转换为最多，最少的问题，我们可以转换为

辅音字母至少为k+1 - 至少为 k 个

---

class Solution {
public:
    long long countOfSubstrings(string word, int k) {
        return fun(word,k)-fun(word,k+1);
    }

    long long fun(string word,int k){
        set<int> s; s.insert('a'); s.insert('e'); s.insert('i'); s.insert('o'); s.insert('u');
        map<int,int> mp;
        int l=0;
        int num1 =0,num2 = 0;
        long long ans = 0;
        for(int r=0;r<word.size();r++){
            int u = word[r];
            if(s.contains(u)){
                mp[u]++;
                if(mp[u]==1){
                    num1++;
                }
            }else{
                num2++;
            }
            while(num1==5&&num2>=k){
                int u = word[l];
                if(s.contains(u)){
                    mp[u]--;
                    if(mp[u]==0) num1--;
                }else{
                    num2--;
                }
                l++;
            }
            ans += l;
        }
        return ans;
    }
};

这里有一个细节，就是我们的每次循环都会加上我们的左端点，因为我们的右端点在扩展的时候，即使是一些无效扩展，我们每次前面计算的答案都是合法的

原文地址：https://blog.csdn.net/wniuniu_/article/details/142644678

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！