第12天(中等题 越长越合法滑动窗口)

打卡第十二天
2道中等题

不定长滑动窗口: 越长越合法
一般要写 ans += left。

内层循环结束后，[left,right] 这个子数组是不满足题目要求的，但在退出循环之前的最后一轮循环，[left−1,right] 是满足题目要求的。由于子数组越长，越能满足题目要求，所以除了 [left−1,right]，还有 [left−2,right], [left−3,right], …, [0,right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 0, 1, 2, …, left−1 的所有子数组都是满足要求的，一共有 left 个。

例题

给你一个字符串 s ，它只包含三种字符 a,b和c。请你返回a,b和c都至少出现过一次的子字符串数目。

class Solution {
public:int numberOfSubstrings(string s) {int left = 0,ans = 0,cnt[3]{};for(char c: s){cnt[c - 'a']++;while(cnt[0] && cnt[1] && cnt[2]){cnt[s[left] - 'a']--;left++;}ans += left;}        return ans;}
};

获取数组nums中最大值m:

// C++20 新写法
int m = ranges::max(nums);// 传统写法1
int m = *max_element(nums.begin(), nums.end());// 传统写法2  
int m = 0;
for(int num : nums) {m = max(m, num);
}

耗时≈半小时 明天继续