初识滑动窗口：【643. 子数组最大平均数 I】

绝地灬酷狼 2022-09-03 12:28 427阅读 0赞

> 滑动窗口指的是这样一类问题的求解方法，在数组上通过双指针同向移动而解决的一类问题。其实这样的问题我们可以不必为它们专门命名一个名字，它们的解法其实是很自然的。  
> 使用滑动窗口解决的问题通常是暴力解法的优化，掌握这一类问题最好的办法就是练习，然后思考清楚为什么可以使用滑动窗口。

## 题目 ##

**子数组最大平均数 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（正解） ##

> **以下图片引用自力扣** https://leetcode-cn.com/problems/maximum-average-subarray-i/solution/zi-shu-zu-zui-da-ping-jun-shu-i-by-leetc-us1k/

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]  
上述过程可以看成维护一个长度为 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;
        }

我是Zhongger，关注我的公众号，带你畅游后端知识  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70]: /images/20220829/ae9a0cd8ff424c259c07abf9ed35063e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzM5NTkxMQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/9395942f07c7489a887dc04bad01dc70.png