滑动窗口专题

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n=nums.size();
        int res = n+1;
        int l=0;
		// r先滑动
        for(int r=0;r<n;++r) {
            s-=nums[r];
            while(s<=0) {
				// s<=0 即 l~r 元素的和恰好满足和 >= s
				// 取最小值，l再向前滑动
                res = min(res, r-l+1);
                s+=nums[l++];
            }
        }
        return res % (n+1);
    }
};

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int count = 0;
        vector<int> m;
        m.push_back(-1);
        for(int i=0;i<n;++i) {
            if (nums[i]&1) m.push_back(i);
        }
        m.push_back(n);
        if (m.size()-2 < k) return 0;
        
        int l=1;
        int r=k;
        while(r<m.size()-1) {
            int a = m[l] - m[l-1] - 1;
            int b = m[r+1] - m[r] - 1;
            count += 1 + a + b + a*b;
            ++l;
            ++r;
        }
        return count;
    }
};

class Solution {
public:
    int balancedString(string s) {
        unordered_map<int, int> count;
        count.insert({'Q', 0});
        count.insert({'W', 0});
        count.insert({'E', 0});
        count.insert({'R', 0});
        for(int c : s) count[c]++;
        
        int i=0;
        int n=s.size();
        int k=n/4;
        int res = n;
        for(int j=0;j<n;++j) {
			// 窗口外出现的次数
            count[s[j]]--;
			// 满足<=k
            while(i<n && count['Q']<=k && count['W']<=k && count['E']<=k && count['R']<=k) {
				// 取最小的结果
                res = min(res, j-i+1);
				// 直到不满足条件为止
                count[s[i++]]++;
            }
        }
        if (res == n) return 0;
        return res;
    }
};