LeetCode | 643 | 子数组最大平均数 | 双指针 | 滑动窗口

双指针在一定条件下可以转化成滑动窗口，这道题就是个很好的例子

---

LeetCode链接：643. 子数组最大平均数 I

---

1.题目描述

给你一个由 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 <= 10^5$
• $-10^4 <= nums[i] <= 10^4$

2.题解

2.1 暴力解法（超出时间限制）

public class Solution {
    public double findMaxAverage(int[] nums, int k) {
        // 初始化最大平均值为负无穷
        double maxAverage = Double.NEGATIVE_INFINITY;

        // 遍历数组中的所有可能的长度为 k 的连续子数组
        for (int i = 0; i <= nums.length - k; i++) {
            // 计算当前子数组的和
            int sum = 0;
            for (int j = i; j < i + k; j++) {
                sum += nums[j];
            }
            // 计算当前子数组的平均值
            double average = (double) sum / k;
            // 更新最大平均值
            maxAverage = average > maxAverage ? average : maxAverage;
        }

        // 返回最大平均值
        return maxAverage;
    }
}

2.2 双指针

• 由于每次都要计算平均值，所以在这里做一个处理，先求出长度为k的区间和的最大值，返回时再求平均

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        // 初始化最大和为最小整数值
        int maxSum = Integer.MIN_VALUE;
        // 左右指针初始化
        int left, right;
        // 当前窗口的和
        int sum = 0;
        
        // 遍历数组
        for (left = 0, right = 0; right < nums.length; right++) {
            // 将当前元素加入窗口和
            sum += nums[right];
            
            // 如果当前窗口大小等于 k，更新最大和
            if (right - left + 1 == k) {
                maxSum = Math.max(maxSum, sum);
            }
            
            // 当窗口大小大于等于 k 时，移动左指针
            while (right - left + 1 >= k) {
                // 将窗口左边界的元素移出和
                sum -= nums[left];
                // 移动左指针
                left++;
            }
        }
        
        // 返回最大和对应的平均值
        return (double) maxSum / k;
    }
}

2.3 双指针优化=>滑动窗口

• 由于所求的窗口的长度是固定的，因此首先计算出数组前k个区间的和，然后再向后滑动区间

public class Solution {
    public double findMaxAverage(int[] nums, int k) {
        // 计算第一个长度为 k 的子数组的和
        int maxSum = 0;
        for (int i = 0; i < k; i++) {
            maxSum += nums[i];
        }

        // 当前子数组的和
        int currentSum = maxSum;

        // 使用滑动窗口遍历数组中的其他可能的长度为 k 的连续子数组
        for (int i = k; i < nums.length; i++) {
            // 更新当前子数组的和
            currentSum = currentSum - nums[i - k] + nums[i];

            // 更新最大和
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }

        // 返回最大平均值
        return (double) maxSum / k;
    }
}