寒假刷题Day13
一、2537. 统计好子数组的数目
class Solution {
public:
long long countGood(vector<int>& nums, int k) {
long long ans = 0;
unordered_map<int, int> cnt;
int pairs = 0, left = 0;
for (int x : nums) {
pairs += cnt[x]++;
while (pairs >= k) {
pairs -= --cnt[nums[left]];
left++;
}
ans += left;
}
return ans;
}
};来自gpt的解析：
题目解释
我们有一个数字排成的队列，比如 [1, 2, 1, 1]。现在需要找出一些连续的数字段（叫“子数组”），满足：
- 里面有 至少 k 对重复的数字。
- 什么是“重复对”？ 就是两个数字一样，比如
[1, 1]里面就有 1 对重复。
我们的目标是数一数有多少这样的子数组。
生活比喻
想象有一群小朋友排队玩游戏，比如 [1, 2, 1, 1]，每个数字表示一个小朋友的队号（比如 1 号小朋友、2 号小朋友）。我们要找出一些连续的小队伍，里面至少有 k 对关系特别好的小朋友（即同队号的小朋友）。
代码解读
1. 初始化准备
long long ans = 0; unordered_map<int, int> cnt; int pairs = 0, left = 0;
翻译：
ans是用来数“有多少满足条件的队伍”的，开始的时候是 0。cnt是一个点名簿，记录小队伍里每个数字出现了多少次。pairs是“队伍里有多少对关系好的小朋友”。left是队伍的最前面，开始时大家都站在原地。
2. 开始逐个看小朋友
for (int x : nums) { pairs += cnt[x]++;
翻译：
- 每次我们都往队伍后面加一个小朋友（
x表示当前小朋友的队号）。 - 把这个小朋友加入点名簿，同时更新有多少对关系好的小朋友。
- 比如，之前有 1 个 1，现在又加了一个 1，就多了一对关系好的（两个 1）。
3. 如果关系好的小朋友太多了，就缩短队伍
while (pairs >= k) { pairs -= --cnt[nums[left]]; left++; }
翻译：
- 如果队伍里的“关系好的小朋友”太多了（达到或超过了 k 对），我们就需要把队伍最前面的小朋友移走。
- 把最前面的小朋友移出队伍时：
- 点名簿上要给他减 1。
- 如果他走了，队伍里关系好的小朋友数量会减少。
- 队伍的最前面位置往后移一个。
4. 计算满足条件的队伍数量
ans += left;
翻译：
- 只要队伍里关系好的小朋友够多，就说明队伍的最前面（
left）之前的所有位置都可以形成合格的小队伍。 - 比如，如果
left = 3，说明有 3 个小队伍符合要求。
5. 返回结果
return ans;
翻译：
- 把所有找到的符合条件的小队伍加起来，最后返回结果。
举例 1
输入：
nums = [1, 1, 1, 1], k = 3
过程：
- 队伍里只有第 1 个 1，关系对数是 0，不够。
- 队伍里有前 2 个 1，关系对数是 1，不够。
- 队伍里有前 3 个 1，关系对数是 3，刚好够：
- 缩短队伍，最前面的 1 被移走，
left = 1，有 1 个符合条件的子数组。
- 缩短队伍，最前面的 1 被移走，
- 队伍里有后 3 个 1，关系对数还是 3：
- 再缩短队伍，最前面的 1 被移走，
left = 2，有 2 个符合条件的子数组。
- 再缩短队伍，最前面的 1 被移走，
最终答案：1 + 2 = 3
举例 2
输入：
nums = [1, 2, 1, 1], k = 2
过程：
- 队伍开始：只有第 1 个 1，关系对数是 0，不够。
- 队伍里有前 2 个数字
[1, 2]，关系对数是 0，不够。 - 队伍里有前 3 个数字
[1, 2, 1]，关系对数是 1，不够。 - 队伍里有
[1, 2, 1, 1]，关系对数是 2，刚好够：- 缩短队伍，最前面的 1 被移走，
left = 1，有 1 个符合条件的子数组。 - 再缩短队伍，
[2, 1, 1]，left = 2，有 2 个符合条件的子数组。
- 缩短队伍，最前面的 1 被移走，
最终答案：1 + 2 = 3
举例 3
复制编辑
nums = [1, 2, 3, 4], k = 1
过程：
- 这时候，每个数字都可以是一个“好子数组”，因为 k = 1，只需要 1 对关系好的小朋友。
[1]、[2]、[3]、[4]都符合要求。
最终答案：4
总结
可以把这个算法看成两部分：
- 滑动窗口找子数组：动态调整队伍的长度，保证满足“至少 k 对关系好的小朋友”。
- 累加子数组数量：每次调整后，把符合条件的小队伍都数出来。
希望这样解释够简单啦！如果还有不懂的地方，继续问我喵~ (＾• ω •＾)
二、713. 乘积小于 K 的子数组
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if(k <= 1) return 0;
int ans = 0;
int left = 0;
int product = 1;
for(int right = 0; right < nums.size(); right++){
product *= nums[right];
while(product >= k){
product /= nums[left];
left++;
}
ans += (right - left + 1);
}
return ans;
}
};为什么“越短越合法”类型题目是 ans += (right - left + 1)？
因为表面上看虽然并没有枚举当前窗口的所有子数组，但是这个right - left + 1表示的是以right结尾的子数组数量。在窗口扩大的时候就已经逐步遍历了所有可能的子数组：
-
在滑动窗口中，每次扩展
right，都会计算所有以nums[right]结尾的子数组。- 这些子数组是新的，未被之前的窗口包含过的。
- 例如，当
right = 2时，计算的是[3],[2, 3],[1, 2, 3]。
-
只计算以
nums[right]结尾的子数组，可以避免重复。- 在窗口
[left, right]中，已经包含了[1, 2]等子数组。 - 如果再次枚举
[1, 2]，就会重复。
- 在窗口
-
每次更新
ans时，right - left + 1正好对应当前窗口新增的子数组数量。
三、3258. 统计满足 K 约束的子字符串数量 I
class Solution {
public:
int countKConstraintSubstrings(string s, int k) {
int ans = 0, left = 0, cnt[2]{};
for(int right = 0; right < s.size(); right++){
cnt[s[right] - '0']++;
while(cnt[0] > k && cnt[1] > k){
cnt[s[left] - '0']--;
left++;
}
ans += (right - left + 1);
}
return ans;
}
};一开始我把判断条件while(cnt[0] > k && cnt[1] > k) 里的 || 写成了 && 。导致了不通过，因为题意是二者满足其一就行，所以反过来说要证否需要二者都不满足。
四、2302. 统计得分小于 K 的子数组数目
class Solution {
public:
long long countSubarrays(vector<int>& nums, long long k) {
long long ans = 0, left = 0;
long long sum = 0;
for(int right = 0; right < nums.size(); right++){
sum += nums[right];
while(sum * (right - left + 1) >= k){
sum -= nums[left];
left++;
}
ans += (right - left + 1);
}
return ans;
}
};