2.3.3 恰好型滑动窗口

恰好型约束常用“至多 k”转化：恰好 k = 至多 k - 至多 k - 1。

恰好型滑动窗口转化图
恰好型滑动窗口：把难直接维护的“恰好”拆成两个“至多”问题相减。

1. Binary Subarrays With Sum

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    int solve(vector<int>& nums, int goal) {
        int ans = 0;
        int sum = 0;
        int l = 0, n = nums.size();
        for(int r = 0; r < n; r++){
            sum += nums[r];

            while(l <= r && sum >= goal){
                sum -= nums[l];
                l++;
            }

            ans += l;
        }
        return ans;
    }

public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        return solve(nums, goal) - solve(nums, goal + 1);
    }
};

2. Count Number Of Nice Subarrays

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    int solve(vector<int>& nums, int k){
        int ans = 0;
        int cnt = 0;
        int l = 0, n = nums.size();
        for(int r = 0; r < n; r++){
            if(nums[r] % 2 == 1){
                cnt++;
            }

            while(l <= r && cnt >= k){
                if(nums[l] % 2 == 1){
                    cnt--;
                }
                l++;
            }

            ans += l;
        }
        return ans;
    }
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        return solve(nums, k) - solve(nums, k + 1);
    }
};

3. Count Of Substrings Containing Every Vowel And K Consonants II

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    long long solve(string s, int k){
        long long ans = 0;
        map<char, int> vowel;
        int cnt = 0;
        int l = 0, n = s.length();
        for(int r = 0; r < n; r++){
            if(s[r] == 'a' || s[r] == 'e' || s[r] == 'i' || s[r] == 'o' || s[r] == 'u'){
                vowel[s[r]]++;
            }else{
                cnt++;
            }

            while(vowel.size() == 5 && l <= r && cnt >= k){
                if(s[l] == 'a' || s[l] == 'e' || s[l] == 'i' || s[l] == 'o' || s[l] == 'u'){
                    vowel[s[l]]--;
                    if(vowel[s[l]] == 0){
                        vowel.erase(s[l]);
                    }
                }else{
                    cnt--;
                }
                l++;
            }

            ans += l;
        }
        return ans;
    }

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

4. Subarrays With K Different Integers

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    int solve(vector<int>& nums, int k){
        int ans = 0;
        map<int, int> m;
        int l = 0, n = nums.size();
        for(int r = 0; r < n; r++){
            m[nums[r]]++;

            while(m.size() >= k){
                m[nums[l]]--;
                if(m[nums[l]] == 0){
                    m.erase(nums[l]);
                }
                l++;
            }

            ans += l;
        }
        return ans;
    }

public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return solve(nums, k) - solve(nums, k + 1);
    }
};
Aries's Blog