)
打卡第十二天
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);
}
耗时≈半小时 明天继续