1. 题目解析

给定一个整数数组nums且长度为k的下标连续的子数组,并输出该最大平均数

方法一：The first thing I could immediately think of was to use a double pointer,指针P1指向数组的第0号位置,Since the subarrays are consecutive in length,Then another pointerP2Directly points to the first of the arrayk-1号位置,然后计算这个kThe average of the elements is enough,So how do you find the biggest one？
for循环遍历整个数组,开始指针p2指向k-1,p1指向0,直到p2指向nums.length-1即可,This needs to be calculated on every traversalk个元素的平均值,Keep updating this average,直到数组遍历完毕,最后返回这个max_average即可.

该方法比较容易想到,Especially for double pointer ideas,是非常重要的,When writing arithmetic problems, you will often encounter problems solved by using double pointers.But the time complexity of this method is relatively high,是O((n-k)*k),因为要遍历n-k次,每次计算kthe average of the elements,without opening up additional storage space,所以空间复杂度为O1.

方法二：Since you want to traverse the entire array,And why should it be calculated every timek个元素之和,这里,Can go further,在每次遍历的时候,Actually you don't need to calculate all of thisk个元素之和,put this pointerp1和指针p2The enclosed area is regarded as a sliding window,Just calculate the sum of the elements of the first sliding window,When traversing to a new sliding window,All calculations are not required,Just remove the first element of the previous sliding window,Plus the last element of the new window,Because the elements in the middle are the same,不需要重复计算.可以将时间复杂度降为O(max(k, n-k)).

2. 代码解析

我是使用java来写的,如下：

public class findMaxAverage{
    
    public static void main(String[] args) {
    
        System.out.println(Solution1(new int[]{
    1,12,-5,-6,50,3,50}, 4));
        System.out.println(Solution2(new int[]{
    1,12,-5,-6,50,3,50}, 4));
    }

// 使用双指针,时间复杂度为(n-k)*k
    public static double Solution1(int[] nums, int k){
    
        int p1 = 0;
        int p2 = k-1;
        double max_average = Double.MIN_VALUE;
        double sum = 0, average = 0;
        while(p2 <= nums.length-1){
    
            for(int i=p1; i<=p2; i++){
    
                sum += nums[i];
            }
            average = sum / k;
            if(average > max_average){
    
                max_average = average;
            }
            sum = 0;
            average = 0;
            p1++;
            p2++;
        }
        return max_average;
    }

// 使用滑动窗口思想：No need for loop nesting,Just update the sum of each window element,时间复杂度为O=max(k, n-k)
    public static double Solution2(int[] nums, int k){
    
        double sum = 0;      // Count the sum of elements for each window
        int n = nums.length; // 获取数组长度
        // Get the sum of the elements of the first window
        for(int i=0; i<k; i++){
    
            sum += nums[i];
        }
        double max = sum;
        // 滑动窗口,Count the sum of each window,The sum of the new window is obtained by subtracting the first element from the sum of the previous window and adding the last element of the new window
        for(int j=k; j<n; j++){
    
            sum = sum - nums[j-k] + nums[j];
            max = Math.max(sum, max);
        }
        return max / k;
    }
}

The final result printed in the terminal is the same,is the average of the last four elements24.25,It proves that there is no problem with the above implementation.