题目描述
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 $10^{-5}$ 的答案都将被视为正确答案。
示例 1：
1
2
3
| 输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
|
示例 2：
1
2
| 输入：nums = [5], k = 1
输出：5.00000
|
提示：
n == nums.length- 1 <= k <= n <= $10^{5}$
- $-10^{4}$ <= nums[i] <= $10^{4}$
题解
解法一：
使用双指针，从左到右遍历，for 循环累加 K 次，然后与最大的 sum 比较，如果更大，则交换，使得 maxSum 始终是最大的子数组，遍历完毕后，再执行 double 的平均数计算（因为 double 运算更耗时，所以最后才计算平均数）。
但是，此方法超时了。因为 while + for 时间复杂度 $O\left(n^2\right)$ 导致遍历时间过长。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int left{0};
int right{k};
int maxSum = INT_MIN;
int sum{};
while (right <= nums.size()) {
for (int i = left; i < left + k; ++i) {
sum += nums[i];
}
if (sum > maxSum)
maxSum = sum;
left++;
right++;
sum = 0;
}
return static_cast<double>(maxSum) / k;
}
};
|
解法二：
先计算第一个子数组，然后再从第 k 个开始，计算第二个数组，这里减去第一个数组，加上后一个数组的方式，实现累加。
这样，就只有一层 for 循环，时间复杂度为 $O\left(n\right)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int sum = 0;
int n = nums.size();
for (int i = 0; i < k; i++) {
sum += nums[i];
}
int maxSum = sum;
for (int i = k; i < n; i++) {
sum = sum - nums[i - k] + nums[i];
maxSum = max(maxSum, sum);
}
return static_cast<double>(maxSum) / k;
}
};
|
