• 3. 3325.字符至少出現K次的子字符串I(中等，學習優化)

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;}
};

• 4. 2799.統計完全子數組的數目(中等)

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;}
};

• 5. 2537.統計好子數組的數目

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;}
};

• 6. 2495.乘積為偶數的子數組數(中等，學習)

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;}
};