每日算法刷题Day14 5.24:leetcode不定长滑动窗口求子数组个数越长越合法4道题，用时1h20min
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;}
};