使用滑动窗口算法解决“子数组最大平均数”问题

题目：子数组最大平均数
给你一个由 n 个元素组成的整数数组 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
提示：
n == nums.length
1 <= k <= n <= 105
-104 <= nums[i] <= 104

分析：本题主要考察的是滑动窗口算法。
滑动窗口是一个大小可变的窗口，左右两端方向一致地向前滑动。它其实是双指针算法中的一个特例。一个指针指向窗口第一个元素，一个指针指向窗口最后一个元素，两个指针之间的间隔是固定的，也就是说两个指针以相同的频率往后移动。（其他双指针：快慢指针，两指针移动频率不一样。左右指针，两指针移动方向不一样。）
步骤：
1、计算出第一个窗口的求和值sum。
2、找出移动前和移动后窗口求和之间的关系。针对这道题，就是每移动一个元素，减掉窗口第一个元素值，加上窗口后面一个元素值，即：sum = sum – nums[i – k] + nums[i];
3、比较移动窗口前后两个窗口的求和哪个大，保存较大的值，继续移动窗口并比较。

package od1;

/**
 * 子数组最大平均数
 * 给一个整数数组，找出平均数最大且长度为 k 的下标连续的子数组，并输出该最大平均数。
 * 原文地址：https://www.codernav.com/2841.html
 * 更多算法详解：https://www.codernav.com
 */
public class OdTest30 {
    public static void main(String[] args) {
        double result = f(new int[]{1, 12, -5, -6, 50, 3}, 4);
        System.out.println(result);
    }

    private static double f(int[] nums, int k) {
        int sum = 0;
        // 找到第一个窗口的值
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int max = sum;
        // 注意i从k开始遍历
        for (int i = k; i < nums.length; i++) {
            // 减去第一个元素的值，加上当前元素的值
            sum = sum - nums[i - k] + nums[i];
            // 求上次求和与这次求和的最大值
            max = Math.max(sum, max);
        }

        return 1.0 * max / k;

    }
}