求最大平均子数组

Question

这是一道 Leetcode 问题， 给定一个由 n 个元素组成的整数数组 nums 和一个整数 k。找到一个长度等于 k 且平均值最大的连续子数组并返回该值。任何计算误差小于 10-5 的答案都将被接受。

示例1：

输入：nums = [1,12,-5,-6,50,3], k = 4 输出：12.75000 解释：最大平均值为 (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

我觉得我已经很接近了，但是有一些我无法弄清楚的小逻辑错误。请帮帮我。这是我到目前为止编写的代码：

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int sum=0;
        double avg;
        double maxavg=0.0;
        for(int i=0;i<n-k+1;i++)
        {
            for(int j=0;j<k;j++)
            {
                sum = sum+nums[i+j];
            }
            avg=((double)sum/(double)k);
            maxavg = Math.max(avg,maxavg);
        }
        return maxavg;
    }
}

Answer 1

为此您不需要双循环。只需迭代数字数组，从一端删除数字并在另一端添加数字即可。

int sum = 0;
int max = 0;
for (int i = 0; i < k; i++) {
  sum = sum + nums[i];
}
max = sum;
for (int i = k; i < nums.length; i++) {
  sum = sum - nums[i - k] + nums[i];
  max = Math.max(sum, max);
}
double avg = max / (double) k;