# 第84期-基础技巧：滑动窗口 子数组最大平均数
Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。
# 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
初始代码
from typing import List
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
#在此之间填写代码
print(Solution().findMaxAverage([1,12,-5,-6,50,3],4))
print(Solution().findMaxAverage([5],1))
2
3
4
5
6
7
# 2 解题思路
- 标签：滑动窗口
- 先算出数组从0下标到k-1下标之间的和sum, max=sum;
- 遍历从下标1开始到nums长度-1之间范围的元素，每次sum先减去i-1(上一个元素的值)，再加上i+k-i的值，即窗口内最后一值，再与max作比较；
- 最终返回平均值
# 3 解题方法
from typing import List
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
i,a=1,len(nums)
t=x=sum(nums[0:k])
while i+k<a+1:
x=x-nums[i-1]+nums[i+k-1]
if t<x:
t=x
i+=1
return t/k
print(Solution().findMaxAverage([1,12,-5,-6,50,3],4))
print(Solution().findMaxAverage([5],1))
2
3
4
5
6
7
8
9
10
11
12
13
14
第1-3，13-14行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 定义变量i,a分别赋值1和nums列表的长度
第5行： 定义变量t，x并赋值nums前k个元素的和
第6行： 当i+k小于等于列表长度时，之后便无法截取k长度的列表了
第7行： 滑动窗口，改变x的值为新窗口的和
第8-9行： 判断该和是否大于t，是则赋值给t
第10行： i加一用于下次遍历
第11行： 返回平均值
代码运行结果为：
# 算法讲解
这里用到了基础技巧：滑动窗口，简单讲解下这个技巧：
什么是滑动窗口
滑动窗口，顾名思义，就是有一个大小可变的窗口，左右两端方向一致的向前滑动（右端固定，左端滑动；左端固定，右端滑动）。
可以想象成队列，一端在push元素，另一端在pop元素，如下所示：
假设有数组[a b c d e f g h]
一个大小为3的滑动窗口在其上滑动,则有:
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]
2
3
4
5
6
7
8
适用范围
- 1、一般是字符串或者列表
- 2、一般是要求最值（最大长度，最短长度等等）或者子序列
算法思想
- 1、在序列中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个窗口。
- 2、先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的序列符合要求。
- 3、此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的序列不再符合要求。同时，每次增加 left前，都要更新一轮结果。
- 4、重复第 2 和第 3 步，直到 right 到达序列的尽头。
思路其实很简单：第 2 步相当于在寻找一个可行解，然后第 3 步在优化这个可行解，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。
# 4 视频解析
高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码 