当前位置：首页 > news >正文

滑动窗口算法-day7（越长越合法子数组）

news 2025/3/11 18:38:23

1.包含所有三种字符的子字符串

题目

解析

1.解析

遍历右指针，当满足条件的时候，再去收缩左指针，达到不满足条件；
此时左指针 L 的值即为当前滑窗下的答案，继续遍历；

代码

class Solution {
public:int numberOfSubstrings(string s) {// 时间复杂度：O(n)// 空间复杂度：O(3)int n = s.size();int ans = 0;unordered_map<char,int> cnt;int l = 0;for(int r = 0;r < n;r ++){ // 遍历右指针cnt[s[r]] ++;// 在满足条件情况下，不断收缩左指针，直到不满足while(cnt['a'] > 0 && cnt['b'] > 0 && cnt['c'] > 0){cnt[s[l]] --;l ++;}ans += l; // 此时 l 就是该滑窗条件下对应答案数}return ans;}
};

2.字符至少出现 K 次的子字符串 I

题目

解析

同理可得

代码

class Solution {
public:int numberOfSubstrings(string s, int k) {// 时间复杂度：O(n)// 空间复杂度：O(k)int n = s.size();int ans = 0;unordered_map<char,int> cnt;int l = 0;for(int r = 0;r < n;r ++){cnt[s[r]] ++;while(cnt[s[r]] >= k) {cnt[s[l]] --;l ++;}ans += l;}return ans;}
};

3.统计完全子数组的数目

题目

解析

同理可得

代码

class Solution {
public:int countCompleteSubarrays(vector<int>& nums) {// 时间复杂度：O(n)// 空间复杂度：O(n)int n = nums.size();int ans = 0;// unordered_set 自动去重，再利用.size()得到不同元素个数int x = unordered_set<int>(nums.begin(),nums.end()).size();unordered_map<int,int> cnt;int l = 0;for(int r = 0;r < n;r ++){cnt[nums[r]] ++;while(cnt.size() == x) {cnt[nums[l]] --;if(cnt[nums[l]] == 0) cnt.erase(nums[l]);l ++;}ans += l;}return ans;}
};

4.统计好子数组的数目

题目

解析

1.解析

核心：用 sum = cnt[nums[i]] 记录“下标对”的数目

代码

class Solution {
public:long long countGood(vector<int>& nums, int k) {// 时间复杂度：O(n)// 空间复杂度：O(n)int n = nums.size();long long ans = 0;int pairs = 0;unordered_map<int,int> cnt;    int l = 0;for(int r = 0;r < n;r ++){pairs += cnt[nums[r]]; // 记录有几对下标cnt[nums[r]] ++; while(pairs >= k){cnt[nums[l]] --;pairs -= cnt[nums[l]];l ++;} ans += l;}return ans;}
};

5.统计重新排列后包含另一个字符串的子字符串个数 II

题目

解析

与《最小覆盖子串》是一样的解法；
核心思想：当子串可以包含字符串，经过重排，就能使得它覆盖字符串；当我们找到了最长包含字符串所有元素的子串时，收缩左端点，直到不能完全覆盖，此时答案 + L；

代码

class Solution {
public:long long validSubstringCount(string word1, string word2) {// 时间复杂度：O(n)// 空间复杂度：O(k)int n = word1.size();int less = 0;long long ans = 0;unordered_map<char,int> cnt;for(char c : word2) {if(cnt[c] == 0) less ++;cnt[c] ++; }int l = 0;for(int r = 0;r < n;r ++){cnt[word1[r]] --;if(cnt[word1[r]] == 0) less --;while(less == 0){if(cnt[word1[l]] == 0) less ++;cnt[word1[l]] ++;l ++;}ans += l;}return ans;}
};