题目
子数组最大平均数 I
给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
例如：
输入：[1,12,-5,-6,50,3], k = 4 输出：12.75 解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
解法1（啪的一下，超时了）
public double findMaxAverage(int[] nums, int k) { int left = 0; int right = k - 1; int max = Integer.MIN_VALUE; while (right < nums.length) { int sum = getSum(nums, left, right); if (max < sum) { max = sum; } right++; left++; } return (double) max / k; } public int getSum(int[] nums, int left, int right) { int sum = 0; for (int i = left; i <= right; i++) { sum += nums[i]; } return sum; }
对于长度为n的数组，当k≤n时，有n-k+1个长度为k的子数组。如果直接计算每个子数组的元素和，时间复杂度过高，无法通过全部测试用例，因此需要使用时间复杂度更低的方法计算每个子数组的元素和。
解法2（正解）
上述过程可以看成维护一个长度为 k 的滑动窗口。
public double findMaxAverage(int[] nums, int k) { int sum = 0; for (int i = 0; i < k; i++) { sum += nums[i]; } int maxSum = sum; for (int i = k; i < nums.length; i++) { sum = sum - nums[i - k] + nums[i]; maxSum = Math.max(sum, maxSum); } return 1.0 * maxSum / k; }
