LeetCode最大子数组平均值问题代码调试求助

我太懂这种“差一步就对但就是找不到问题”的感觉了！别着急，咱们来一点点拆解你的代码问题：

首先看你的核心问题：

• sum变量未重置：你只在代码开头初始化了一次sum=0，但每次外层循环计算新的子数组和时，sum会在上一次的结果上继续累加，完全偏离了正确的子数组和。比如第一次i=0时sum是1+12-5-6=2，到i=1时，sum会在2的基础上再加12-5-6+50，得到的结果根本不是第二个窗口的正确和，自然会算出错误的平均值。
• maxavg初始值不合理：你把maxavg设为0.0，如果所有子数组的平均值都是负数（比如nums=[-1,-2,-3],k=2），那你的代码会错误返回0.0，而正确结果应该是-1.5。

先给你修正后的基础版本代码，解决这两个问题：

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        double maxavg = Double.NEGATIVE_INFINITY; // 初始化为负无穷，覆盖所有可能的负数情况

        for(int i=0;i<n-k+1;i++){
            int sum=0; // 每次外层循环都重置sum，确保计算当前窗口的和
            for(int j=0;j<k;j++){
                sum += nums[i+j];
            }
            double avg = (double)sum / k;
            maxavg = Math.max(avg, maxavg);
        }
        return maxavg;
    }
}

不过这里还要提一句，你的双重循环时间复杂度是O(n*k)，当n很大的时候（比如LeetCode的测试用例n到10^5），这个代码会超时。所以更优的方法是用滑动窗口，把时间复杂度降到O(n)：

思路很简单：先计算第一个窗口的和，之后每滑动一次，就减去窗口左边移出的元素，加上右边新进入的元素，这样每次计算sum只需要O(1)时间：

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int currentSum = 0;

        // 计算第一个窗口的和
        for(int i=0;i<k;i++){
            currentSum += nums[i];
        }
        double maxavg = (double)currentSum / k;

        // 滑动窗口遍历剩余元素
        for(int i=k;i<n;i++){
            currentSum = currentSum - nums[i-k] + nums[i];
            double avg = (double)currentSum / k;
            maxavg = Math.max(maxavg, avg);
        }
        return maxavg;
    }
}

这样既解决了逻辑错误，又优化了性能，应该就能通过所有测试用例啦！

备注：内容来源于stack exchange，提问作者Bhoomika