4. 2875.无限数组的最短子数组(中等,学习)
2875. 无限数组的最短子数组 - 力扣（LeetCode）
思想
1.下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。请你从 infinite_nums 中找出满足 元素和 等于 target 的 最短 子数组，并返回该子数组的长度。如果不存在满足条件的子数组，返回 -1 。
2.我的想法是infinite_nums由无数个nums组合而来，但是左端点left不能超过n，因为如果超过n说明可以向左平移让left在[0,n)之间，所以最外层while循环条件为left<n,但是最后两个测试点会超时，因为n很大情况下，子数组不存在满足条件，left要在内部while循环sum>target成立条件下才能右移，会出现right和left交替右移的情况，耗时很长。
3.学习另一种思想:
因为nums数组totalSum已知，而如果target覆盖多个nums数组，一定能写成如下形式:
target=k*totalSum+target%totalSum
所以问题转变为求两个nums范围内，和为target%totalSum的最小长度minRem,然后答案为minRem+k*n
如下图所示
4.保持left和right的右移，要映射到数组上才取余n，而不是让left和right加1就取余n，会导致算长度变复杂
代码
c++:
1.我的
class Solution {
public:
int minSizeSubarray(vector<int>& nums, int target) {
int n = nums.size();
int res = INT_MAX;
long long sum = 0;
int left = 0, right = 0;
while (left < n) { // 会超时
sum += nums[right % n];
while (sum > target) {
sum -= nums[left % n];
++left; // 特定条件left才右移
}
if (sum == target)
res = min(res, right - left + 1);
++right;
}
if (res == INT_MAX)
return -1;
return res;
}
};
2.学习
class Solution {
public:
int minSizeSubarray(vector<int>& nums, int target) {
int n = nums.size();
int res = INT_MAX;
long long sum = 0, totalSum = 0;
for (int x : nums)
totalSum += x;
int left = 0;
int k = target / totalSum, rem = target % totalSum;
for (int right = 0; right < 2 * n; ++right) {
sum += nums[right % n];
while (sum > rem) {
sum -= nums[left % n];
++left;
}
if (sum == rem)
res = min(res, right - left + 1);
}
if (res == INT_MAX)
return -1;
return res + k * n;
}
};
剩下两道困难第2轮再刷
2.3 求子数组个数
模版套路
套路
题目描述
学习经验
1.求个数开long long res
2.3.1 越长越合法
一般要写 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 个。
class Solution {
public:
int numberOfSubstrings(string s) {
int n = s.size();
int res = 0;
unordered_map<char, int> cnt;
int left = 0;
for (int right = 0; right < n; ++right) {
// 1. 入窗口
++cnt[s[right]];
// 2. 满足条件进入while循环
while (cnt['a'] >= 1 && cnt['b'] >= 1 && cnt['c'] >= 1) {
--cnt[s[left]];
++left;
}
// 3.
// 此时[left,right]不满足条件，但[left-1,right]满足条件，对于当前固定的right,新增了[0,left-1]共left个答案
res += left;
}
return res;
}
};
1.给你一个字符串 s ，它只包含三种字符 a, b 和 c 。请你返回 a，b 和 c 都 至少 出现过一次(窗口条件)的子字符串数目。
2.给你一个整数数组 nums 和一个 正整数 k 。请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次(窗口条件)的子数组，并返回满足这一条件的子数组的数目。
(注意:题目说的最大元素指整个 nums 数组的最大值，不是子数组的最大值。)
1.相比于2.1和2.2求最长或最短满足条件的窗口大小，2.3求子数组个数是要求所有满足条件的窗口个数，所以右端点right更新到某一个值固定后，让left右移直到不满足条件，使得[left,right]不满足条件，而[left-1,right]满足条件，新增了[0,left-1]共left个答案
2.得保证[left,right]不满足条件，但[left-1,right]刚好满足条件，且[[0,left-1],right]都满足条件，res才能+left个
1358. 包含所有三种字符的子字符串数目 - 力扣（LeetCode）
思想
1.给你一个字符串 s ，它只包含三种字符 a, b 和 c 。请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。
代码
class Solution {
public:
int numberOfSubstrings(string s) {
int n = s.size();
int res = 0;
unordered_map<char, int> cnt;
int left = 0;
for (int right = 0; right < n; ++right) {
// 1. 入窗口
++cnt[s[right]];
// 2. 满足条件进入while循环
while (cnt['a'] >= 1 && cnt['b'] >= 1 && cnt['c'] >= 1) {
--cnt[s[left]];
++left;
}
// 3.
// 此时[left,right]不满足条件，但[left-1,right]满足条件，对于当前固定的right,新增了[0,left-1]共left个答案
res += left;
}
return res;
}
};
2962. 统计最大元素出现至少 K 次的子数组 - 力扣（LeetCode）
1.给你一个整数数组 nums 和一个 正整数 k 。请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。
注意:题目说的最大元素指整个 nums 数组的最大值，不是子数组的最大值。所以需要提取得到nums数组最大值，而不是在遍历中动态更新
c++:
class Solution {
public:
long long countSubarrays(vector<int>& nums, int k) {
int n = nums.size();
long long res = 0;
int maxVal = INT_MIN, maxNum = 0;
for (int x : nums)
maxVal = max(maxVal, x);
int left = 0;
for (int right = 0; right < n; ++right) {
if (nums[right] == maxVal)
++maxNum;
while (maxNum >= k) {
if (nums[left] == maxVal)
--maxNum;
++left;
}
res += (long long)left;
}
return res;
}
};