3325. 字符至少出现 K 次的子字符串 I - 力扣（LeetCode）
思想
1.给你一个字符串 s 和一个整数 k，在 s 的所有子字符串中，请你统计并返回 至少有一个 字符 至少出现 k 次的子字符串总数。
2.我的思路是用unordered_map记录字符次数，但是每次while循环判断条件都要遍历一遍unordered_map,耗时太大
3.学习:只需判断cnt[s[right]]>=k即可，因为当前只有右端点right字符移入窗口增加次数，而对于此刻也只有它有可能超过K(因为每次while循环结束保证都没有字符次数超过K，从而进入下一轮for循环)
4.给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。(窗口条件)(假设当前窗口中值为nums[right]已有x对,那么right元素进来会增加x对，left出去会减少x-1对)
代码
c++:
1.我的代码
class Solution {
public:
bool check(const unordered_map<char, int> cnt, const int k) {
for (auto x : cnt) {
if (x.second >= k)
return true;
}
return false;
}
int numberOfSubstrings(string s, int k) {
int n = s.size();
unordered_map<char, int> cnt;
int res = 0;
int left = 0;
for (int right = 0; right < n; ++right) {
++cnt[s[right]];
while (check(cnt, k)) {
--cnt[s[left]];
++left;
}
res += left;
}
return res;
}
};
2.学习
class Solution {
public:
int numberOfSubstrings(string s, int k) {
int n = s.size();
unordered_map<char, int> cnt;
int res = 0;
int left = 0;
for (int right = 0; right < n; ++right) {
++cnt[s[right]];
while (cnt[s[right]] >= k) {
--cnt[s[left]];
++left;
}
res += left;
}
return res;
}
};
3.拓展，如果题目条件改成统计并返回 至少有两个 字符 至少出现 k 次的子字符串总数，需要再引入一个字符次数变量，也无需全部遍历cnt
class Solution {
public:
int numberOfSubstrings(string s, int k) {
int n = s.size();
unordered_map<char, int> cnt;
int res = 0;
int left = 0;
int charCnt=0;
for (int right = 0; right < n; ++right) {
++cnt[s[right]];
if(cnt[s[right]] == k) ++charCnt;
while (charCnt >= 2) { // 更通用的方法
--cnt[s[left]];
if(cnt[s[left]]==k-1) --charCnt;
++left;
}
res += left;
}
return res;
}
};
2799. 统计完全子数组的数目 - 力扣（LeetCode）
思想
1.如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：子数组中 不同 元素的数目等于整个数组不同元素的数目。返回数组中 完全子数组 的数目。
2.unordered_set计算整个数组不同元素的数目,unordered_map计算子数组中不同元素的数目
3.使用unordered_set<int> st(nums.begin(), nums.end());通过迭代器来初始化构造，方便快捷
代码
c++:
class Solution {
public:
int countCompleteSubarrays(vector<int>& nums) {
int n = nums.size();
int res = 0;
unordered_set<int> st(nums.begin(), nums.end());
unordered_map<int, int> cnt;
int k = st.size();
int left = 0;
for (int right = 0; right < n; ++right) {
++cnt[nums[right]];
while (cnt.size() == k) {
--cnt[nums[left]];
if (cnt[nums[left]] == 0)
cnt.erase(nums[left]);
++left;
}
res += left;
}
return res;
}
};
2537. 统计好子数组的数目 - 力扣（LeetCode）
思想
1.给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。
2.思路:
对于当前的for循环，假设窗口中值为nums[right]已有x对,那么right元素进来会增加x对，left出去会减少x-1对(就是考虑right进来和left出去会对统计量产生什么影响，只要管right和left即可)
代码
c++:
class Solution {
public:
long long countGood(vector<int>& nums, int k) {
int n = nums.size();
long long res = 0;
long long sum = 0;
map<int, long long> cnt;
int left = 0;
for (int right = 0; right < n; ++right) {
sum += cnt[nums[right]];
++cnt[nums[right]];
while (sum >= k) {
--cnt[nums[left]];
sum -= cnt[nums[left]];
++left;
}
res += left;
}
return res;
}
};
2495. 乘积为偶数的子数组数 - 力扣（LeetCode）
思想
1.给定一个整数数组 nums，返回_具有偶数乘积的_ nums 子数组的数目。
2.我的一开始思路是用bool遍历维护奇偶性，但是增加right元素可以，移出left元素就不行了，故还是采用了乘积来判断，会超内存
3.学习:只要窗口内有一个偶数乘积就是偶数，所以转变为偶数个数至少为1的子数组数目
代码
c++:
1.我的
class Solution {
public:
long long evenProduct(vector<int>& nums) {
int n=nums.size();
long long res=0;
unsigned long long product=1;
int left=0;
for(int right=0;right<n;++right){
product*=(unsigned long long)nums[right];
while(!(product&1)){
product/=(unsigned long long)nums[left];
++left;
}
res+=left;
}
return res;
}
};
2.学习
class Solution {
public:
long long evenProduct(vector<int>& nums) {
int n = nums.size();
long long res = 0;
int cnt = 0;
int left = 0;
for (int right = 0; right < n; ++right) {
if (!(nums[right] & 1))
++cnt;
while (cnt >= 1) {
if (!(nums[left] & 1))
--cnt;
++left;
}
res += left;
}
return res;
}
};