滑动窗口

目录

LeetCode209 长度最小的子数组​编辑

LeetCode713 乘积小于K的子数组

LeetCode3 无重复字符的最长子串

LeetCode3306 元音辅音字符串计数II（恰好型滑动窗口）

---

LeetCode209 长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n=nums.size();
        int res=0x3f3f3f3f;
        int sum=0;
        for(int left=0,right=0;right<n;right++){//枚举子数组右端点
            sum+=nums[right];
            while(sum>=target){//满足要求
                res=min(res,right-left+1);
                sum-=nums[left++];//左端点右移
            }
        }
        if(res==0x3f3f3f3f) return 0;
        return res;
    }
};

时间复杂度：O(n)

空间复杂度：O(1) 

LeetCode713 乘积小于K的子数组

区间[l,r]的子数组满足条件，[l,r]，[l+1,r]，... ，[r,r]的子数组都满足条件。 

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k<=1) return 0;
        int n=nums.size();
        int res=0;
        int product=1;
        for(int left=0,right=0;right<n;right++){
            product*=nums[right];
            while(product>=k){ //不满足要求
                product/=nums[left];
                left++;
            }
            res+=right-left+1;
        }
        return res;
    }
};

时间复杂度：O(n)

空间复杂度：O(1) 

LeetCode3 无重复字符的最长子串

 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n=s.size();
        int res=0;
        unordered_map<char,int> h; //维护从下标 left 到下标 right 的每个字符的数量
        for(int left=0,right=0;right<n;right++){
            h[s[right]]++;
            //如果窗口内已经包含 c，那么再加入一个 c 会导致窗口内有重复元素
            //所以要在加入 c 之前，先移出窗口内的 c
            while(h[s[right]]>1){ //窗口内有 c
                h[s[left]]--; //缩小窗口
                left++;
            }
            res=max(res,right-left+1); //更新窗口长度最大值
        }
        return res;
    }
};

时间复杂度：O(n)

空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小，本题中字符均为 ASCII 字符，所以 ∣Σ∣≤128

LeetCode3306 元音辅音字符串计数II（恰好型滑动窗口）

恰好型滑动窗口：转换成两个至少型滑动窗口

问题等价于如下两个问题：

每个元音字母至少出现一次，并且至少包含 k 个辅音字母的子串个数。记作 f(k)。
每个元音字母至少出现一次，并且至少包含 k+1 个辅音字母的子串个数。记作 f(k+1)。
二者相减，所表达的含义就是恰好包含 k 个辅音字母了，所以答案为 f(k)- f(k+1)

class Solution {
public:
    bool judge(int a,int e,int i,int o,int u,int fu,int k){
        if(a>=1&&e>=1&&i>=1&&o>=1&&u>=1&&fu>=k) return true;
        return false;
    }
    long long f(string word,int k){
        int n=word.size();
        long long res=0;
        int a=0,e=0,i=0,o=0,u=0;
        int fu=0;
        vector<int> h(5,0);
        for(int left=0,right=0;right<n;right++){
            if(word[right]=='a') a++;
            else if(word[right]=='e') e++;
            else if(word[right]=='i') i++;
            else if(word[right]=='o') o++;
            else if(word[right]=='u') u++;
            else fu++;
            while(judge(a,e,i,o,u,fu,k)){
                if(word[left]=='a') a--;
                else if(word[left]=='e') e--;
                else if(word[left]=='i') i--;
                else if(word[left]=='o') o--;
                else if(word[left]=='u') u--;
                else fu--;
                left++;
            }
            res+=left;
        }
        return res;
    }
    long long countOfSubstrings(string word, int k) {
        return f(word,k)-f(word,k+1);
    }
};

时间复杂度：O(n)

空间复杂度：O(1) 

原文地址：https://blog.csdn.net/weixin_53287225/article/details/142708994

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