陈东宇的博客

    643. 子数组最大平均数 I

    力扣原题（完整题面）

    题意

    给定数组 nums 和整数 k，在所有长度为 k 的连续子数组中，找出最大的平均值。结果允许 10^-5 以内的误差。

    样例 1

    输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75

    解释：最大平均数为 (12-5-6+50) / 4 = 51 / 4 = 12.75。

    样例 2

    输入：nums = [5], k = 1
输出：5.00000

    解题思路

    窗口长度始终是 k。先让右端点向右走，凑出第一个窗口并计算平均值。之后每轮从总和中减去左端点的数，左端点右移；下一轮再加入右边的新数。这样不需要为每个窗口重新求和。

    代码里的 right 指向下一个要加入的元素。每次计算平均值时，当前窗口恰好是 [left, right)，长度为 k。最后一个窗口计算完后，right 已经到达数组末尾，循环结束。

    我的代码

    class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double maxAvg = -999999999;
        int left = 0, right = 0;
        double sum = 0;
        int len = nums.size();

        while (right < len) {
            while (right - left < k) {
                sum += nums[right];
                right++;
            }
            maxAvg = max(maxAvg, sum / k);
            sum -= nums[left];
            left++;
        }
        return maxAvg;
    }
};

    时间复杂度 O(n)，空间复杂度 O(1)。maxAvg 的初始值低于题目允许的最小平均值，因此不会影响结果。