寒假刷题Day1
一、643. 子数组最大平均数 I
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。
代码：
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int sum = 0;
// 初始化第一个窗口的和
for (int r = 0; r < k; ++r) {
sum += nums[r];
}
// 初始化最大平均值为第一个窗口的平均值
double ans = (double)sum / k;
// 滑动窗口
for (int r = k; r < nums.size(); ++r) {
sum += nums[r] - nums[r - k]; // 同时更新右端增加和左端移除
ans = max(ans, (double)sum / k); // 更新最大平均数
}
return ans;
}
};思路：
核心在于维护滑动窗口内数字总和sum，最后每次滑动完成都比较此次与上次结果大小，用ans保存结果。
二、1343. 大小为 K 且平均值大于等于阈值的子数组数目
给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
代码：
class Solution {
public:
int numOfSubarrays(vector<int>& arr, int k, int threshold) {
int ans = 0;
int sum = 0;
for(int r = 0 ; r < k; ++r){
sum += arr[r];
}
if(sum >= threshold * k){
ans++;
}
for(int r = k; r < arr.size(); ++r){
sum += arr[r] - arr[r - k];
if(sum >= threshold * k){
ans++;
}
}
return ans;
}
};再进一步，精简代码：
class Solution {
public:
int numOfSubarrays(vector<int>& arr, int k, int threshold) {
int ans = 0, sum = 0;
for (int r = 0; r < arr.size(); ++r) {
sum += arr[r]; // 更新当前窗口的总和
// 窗口大小达到 k 时
if (r >= k - 1) {
if (sum >= threshold * k) ans++; // 判断当前窗口是否满足条件
sum -= arr[r - k + 1]; // 移除窗口最左侧元素
}
}
return ans;
}
};
更进一步，要求输出子数组：
class Solution {
public:
vector<vector<int>> findSubarrays(vector<int>& arr, int k, int threshold) {
vector<vector<int>> result; // 用于存储满足条件的子数组
int sum = 0;
for (int r = 0; r < arr.size(); ++r) {
sum += arr[r]; // 更新当前窗口的总和
// 当窗口大小达到 k
if (r >= k - 1) {
if (sum >= threshold * k) {
// 收集当前窗口的子数组
vector<int> subarray(arr.begin() + r - k + 1, arr.begin() + r + 1);
result.push_back(subarray);
}
// 移除窗口最左侧的元素
sum -= arr[r - k + 1];
}
}
return result;
}
};
- 使用
vector<vector<int>> result来存储所有满足条件的子数组。 - 每次满足条件时，通过
arr.begin() + r - k + 1和arr.begin() + r + 1创建当前窗口的子数组。
思路：
基本和上一题一样，每次更新完sum的值后加一步比较sum和平均值*k的大小
三、2090. 半径为 k 的子数组平均值
给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。
半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。
构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。
x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。
- 例如，四个元素
2、3、1和5的平均值是(2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到2。
代码：
class Solution {
public:
vector<int> getAverages(vector<int>& nums, int k) {
// 依然是使用滑动窗口实现
// 窗口为[left,right],且长度为2*k+1,这个1表示当前元素
vector<int> res(nums.size(), -1);
//妙啊，初始化元素为-1，后续减少判断分支
int left = 0;
long long sum = 0;
for (int right = 0; right < nums.size(); right++) {
sum += nums[right];
// 窗口未成形
if (right < 2 * k) {
continue;
}
// 窗口成型，搜集结果
res[left + (right - left) / 2] = sum / (2 * k + 1);
// 移动窗口左边界
sum -= nums[left];
left++;
}
return res;
}
};思路：
1.先判断窗口是否成型（右指针 >= 2*k），成型后再开始维护sum
2.学习这种简化代码的思路，前期能做的事情不要留给后期（指元素全部初始化为-1），我一开始想着判断三部分，答案数组前k个为-1，中间计算平均数，后k个为-1，这样不仅麻烦，也不满足普遍条件。