这类计数题通常先移动右端点扩大窗口；一旦达到合法状态，更长的窗口也会继续合法。
越长越合法：固定右端点时，达到合法后可以统计所有更靠左起点形成的子数组。 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 {
public:
int numberOfSubstrings(string s) {
int ans = 0;
int cnt[3];
int ok = 0;
int l = 0, n = s.length();
for(int r = 0; r < n; r++){
if(cnt[s[r] - 'a'] == 0){
ok++;
}
cnt[s[r] - 'a']++;
while(l <= r && ok == 3){
cnt[s[l] - 'a']--;
if(cnt[s[l] - 'a'] == 0){
ok--;
}
l++;
}
ans += l;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
long long countSubarrays(vector<int>& nums, int k) {
int mx = ranges::max(nums);
int cnt = 0;
long long ans = 0;
int l = 0, n = nums.size();
for(int r = 0; r < n; r++){
if(nums[r] == mx){
cnt++;
}
while(cnt >= k){
if(nums[l] == mx){
cnt--;
}
l++;
}
ans += l;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int numberOfSubstrings(string s, int k) {
int ans = 0;
int cnt[27];
int l = 0;
for(char c : s){
cnt[c - 'a']++;
while(cnt[c - 'a'] >= k){
cnt[s[l] - 'a']--;
l++;
}
ans += l;
}
return ans;
}
};
|
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
| class Solution {
public:
int countCompleteSubarrays(vector<int>& nums) {
set<int> s;
int n = nums.size();
for(int i=0; i<n; i++){
s.insert(nums[i]);
}
int k = s.size();
int l = 0;
int ans = 0;
map<int, int> m;
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;
}
};
|
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 {
public:
long long countGood(vector<int>& nums, int k) {
long long ans = 0;
map<int, int> cnt;
int checked = 0;
int l = 0, n = nums.size();
for(int r=0; r<n; r++){
cnt[nums[r]]++;
if(cnt[nums[r]] > 0)
checked += cnt[nums[r]] - 1;
while(checked >= k){
cnt[nums[l]]--;
checked -= cnt[nums[l]];
if(cnt[nums[l]] == 0){
cnt.erase(nums[l]);
}
l++;
}
ans += l;
}
return ans;
}
};
|
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| class Solution {
public:
long long validSubstringCount(string word1, string word2) {
int diff[26];
for(char c : word2){
diff[c - 'a']++;
}
int less = 0;
for(int d : diff){
if(d > 0) less++;
}
long long ans = 0;
int l = 0, n = word1.length();
for(int r = 0; r < n; r++){
int i = word1[r] - 'a';
diff[i]--;
if(diff[i] == 0){
less--;
}
while(less == 0){
int i = word1[l] - 'a';
if(diff[i] == 0) less++;
diff[i]++;
l++;
}
ans += l;
}
return ans;
}
};
//下面是一开始超内存的：
class Solution {
public:
long long validSubstringCount(string word1, string word2) {
int k[27];
int ksize = 0;
for(char c : word2){
if(k[c - 'a'] == 0)
ksize++;
k[c - 'a']++;
}
long long ans = 0;
int cnt[27];
for(int i=0; i<27; i++){
cnt[i] = 0;
}
set<int> ok;
int l = 0, n = word1.length();
for(int r = 0; r < n; r++){
int i = word1[r] - 'a';
cnt[i]++;
if(k[i] != 0 && cnt[i] >= k[i]) ok.insert(i);
while(l <= r && ok.size() >= ksize){
int i = word1[l] - 'a';
cnt[i]--;
if(k[i] != 0 && cnt[i] < k[i]){
ok.erase(i);
}
l++;
}
ans += l;
}
return ans;
}
};
/*
用diff数组记录差异减少开销（记录出现个数的k和cnt数组就可以缩为一个diff数组），用一个变量
存合法子数组数目，减少set<int>开销。
*/
|
