2.3.1 越短越合法

这类计数题通常先移动右端点扩大窗口；当窗口满足条件后，左端点右移会继续保持合法。

越短越合法的子数组计数图 — 越短越合法：固定右端点时，满足条件后以当前右端点结尾的合法子数组可以一次计数。

1. Subarray Product Less Than K

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int ans = 0;
        int l = 0, pd = 1;
        int n = nums.size();
        for(int r=0; r<n; r++){
            pd *= nums[r];

            while(pd >= k && l <= r){
                pd /= nums[l++];
            }

            ans += r - l + 1;
        }
        return ans;
    }
};

2.https://leetcode.cn/problems/count-substrings-that-satisfy-k-constraint-i/description/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int ans = 0;
        int sum[2];
        int l = 0, n = s.length();
        for(int r=0; r<n; r++){
            sum[s[r] - '0']++;

            while(l <= r && (sum[0] > k && sum[1] > k)){
                sum[s[l] - '0']--;
                l++;
            }

            ans += r - l + 1;
        }
        return ans;
    }
};

2. Count Subarrays With Score Less Than K

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        long long ans = 0;
        long long sum = 0;
        int n = nums.size();
        int l = 0;
        for(int r=0; r<n; r++){
            sum += nums[r];

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

            ans += r - l + 1;
        }
        return ans;
    }
};

3. Continuous 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
27
28
29
30
31
32
33
34
35
class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        deque<int> min_q, max_q;
        long long ans = 0;
        int l = 0;
        int n = nums.size();
        for(int r = 0; r < n; r++){
            int x = nums[r];

            while(!min_q.empty() && x <= nums[min_q.back()]){
                min_q.pop_back();
            }
            min_q.push_back(r);

            while(!max_q.empty() && x >= nums[max_q.back()]){
                max_q.pop_back();
            }
            max_q.push_back(r);

            while(nums[max_q.front()] - nums[min_q.front()] > 2){
                l++;

                if(min_q.front() < l)
                    min_q.pop_front();

                if(max_q.front() < l)
                    max_q.pop_front();
            } 
            
            ans += r - l + 1;
        }
        return ans;
    }
};

4. 1GxJYY

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int beautifulBouquet(vector<int>& flowers, int cnt) {
        int mod = 1e9 + 7;
        int ans = 0;
        map<int, int> m;
        int l = 0, n = flowers.size();
        for(int r = 0; r < n; r++){
            m[flowers[r]]++;
            while(m[flowers[r]] > cnt){
                m[flowers[l]]--;
                l++;
            }
            ans += (r - l + 1) % mod;
        }
        return ans;
    }
};