阿里云盘惊现“一锅端“的 Bug，我刚充的钱啊！
题目描述
平台：LeetCode
题号：643
给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
示例：
输入：[1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
提示：
-
-
所给数据范围
滑动窗口
这是一道道滑动窗口裸题。
以下代码，可以作为滑动窗口模板使用：
-
初始化将滑动窗口压满，取得第一个滑动窗口的目标值
-
继续滑动窗口，每往前滑动一次，需要删除一个和添加一个元素
Java 代码：
class Solution {
public double findMaxAverage(int[] nums, int k) {
double ans = 0, sum = 0;
for (int i = 0; i < k; i++) sum += nums[i];
ans = sum / k;
for (int i = k; i < nums.length; i++) {
sum = sum + nums[i] - nums[i - k]; // int add = nums[i], del = nums[i - k];
ans = Math.max(ans, sum / k);
}
return ans;
}
}
C++ 代码：
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
double ans = 0, sum = 0;
for (int i = 0; i < k; i++) sum += nums[i];
ans = sum / k;
for (int i = k; i < nums.size(); i++) {
sum = sum + nums[i] - nums[i - k];
ans = max(ans, sum / k);
}
return ans;
}
};
Python 代码：
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
ans = 0
sumv = sum(nums[:k])
ans = sumv / k
for i in range(k, len(nums)):
sumv += nums[i] - nums[i - k]
ans = max(ans, sumv / k)
return ans
TypeScript 代码：
function findMaxAverage(nums: number[], k: number): number {
let ans: number = 0, sum: number = 0;
for (let i: number = 0; i < k; i++) sum += nums[i];
ans = sum / k;
for (let i: number = k; i < nums.length; i++) {
sum = sum + nums[i] - nums[i - k];
ans = Math.max(ans, sum / k);
}
return ans;
};
-
时间复杂度：每个元素最多滑入和滑出窗口一次。复杂度为 -
空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉