各位題友大家好，今天是每日算法題公眾號堅持日更的第 11 天。今天力扣上的每日一題是第 643 題「子數組最大平均數 I」。可以通過每日一題的小程序查看題目詳情：
題目大意給定 n 個整數，找出平均數最大且長度為 k 的連續子數組，並輸出該最大平均數。
示例輸入：[1,12,-5,-6,50,3] , k = 4輸出：12.75解釋：最大平均數 (12-5-6+50)/4 = 51/4 = 12.75
數據範圍解題思路首先需要區分兩個概念：子串（子數組） 和 子序列。 這兩個名詞經常在題目中出現，非常有必要加以區分。子串sub-string（子數組 sub-array）是連續的，而子序列 subsequence 可以不連續。
方法一：preSum今天題目讓求最大平均數，由於 k 是不變的，因此可以先求區間的最大和，然後再除以 k。
上周我在題解中已經說過，求區間的和可以用 preSum。preSum 方法還能快速計算指定區間段 i ~ j 的元素之和。它的計算方法是從左向右遍歷數組，當遍歷到數組的 i 位置時，preSum表示 i 位置左邊的元素之和。
假設數組長度為 N，我們定義一個長度為 N+1 的 preSum 數組，preSum[i] 表示該元素左邊所有元素之和（不包含當前元素）。然後遍歷一次數組，累加區間 [0, i) 範圍內的元素，可以得到 preSum 數組。代碼如下：
N = len(nums)
preSum = range(N + 1)
for i in range(N):
preSum[i + 1] = preSum[i] + nums[i]
print(preSum)利用 preSum 數組，可以在 O(1) 的時間內快速求出 nums 任意區間 [i, j] (兩端都包含) 的各元素之和。
sum(i, j) = preSum[i + 1] - preSum[j]
對於本題，可以先遍歷一次，求數組每個位置的 preSum，然後再遍歷一次，求長度為 k 的每個區間的最大和。最終除以 k 得到最大平均數。
preSum使用 Python2 寫的代碼如下。
class Solution(object):
def findMaxAverage(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: float
"""
N = len(nums)
preSum = range(N + 1)
for i in range(N):
preSum[i + 1] = preSum[i] + nums[i]
largest = float("-inf")
for i in range(k - 1, N):
largest = max(preSum[i + 1] - preSum[i + 1 - k], res)
return largest / float(k)
方法二：滑動窗口題目也可以抽象成長度固定為 k 的滑動窗口。當每次窗口右移的時候，需要把右邊的新位置加到窗口中的和中，把左邊被移除的位置從窗口的和中減掉。這樣窗口裡面所有元素的和是準確的，我們求出最大的和，最終除以 k 得到最大平均數。
這個方法只用遍歷一次數組。
需要注意的是，需要根據 i 的位置，計算滑動窗口是否開始、是否要移除最左邊元素：
當 i >= k - 1 時，最左邊第一個滑動窗口內的元素剛好 k 個，開始計算滑動窗口的最大和。當 i >= k 時，為了固定窗口的元素是 k 個，每次移動時需要將 i - k 位置的元素移除。使用 Python2 寫的代碼如下。
class Solution(object):
def findMaxAverage(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: float
"""
sums = 0
largest = float('-inf')
for i, num in enumerate(nums):
sums += num
if i >= k:
sums -= nums[i - k]
if i >= k - 1:
largest = max(sums, largest)
return largest / float(k)
刷題心得今天的題目非常好，雖然是個 Easy 題目，但是讓我們練習了 preSum 和 滑動窗口 兩種方法的最基本用法。
preSum 方法要注意定義的 preSum 是否包含當前元素；歡迎加入刷題群目前已經近 2000 人加入了每日一題打卡群。加入方式是通過每日一題打卡網站。每天都會同步力扣每日一題，這是個互相幫助、互相監督的算法題打卡網站，其地址是 https://www.ojeveryday.com/
想加入千人刷題群的朋友，可以複製上面的連結到瀏覽器，然後在左側點擊「加入組織」，提交力扣個人主頁，即可進入刷題群。期待你早日加入。
也可點擊 「閱讀原文」，直接提交力扣個人主頁。
關於作者我是本文的作者是負雪明燭，畢業於北京郵電大學，目前就職於阿里巴巴。堅持刷算法題 5 年，共計刷了 800 多道算法題。做過的每個算法題都在 CSDN 上寫題解博客，獲得好評無數，CSDN 的累計閱讀量已經 160萬 次！博客地址是：https://blog.csdn.net/fuxuemingzhu
「每日算法題」公眾號是我維護的一個算法題解公眾號，主要講解算法題的解法，也會分享找工作的經驗。歡迎關注。
題目來源：643. 子數組最大平均數 I連結：https://leetcode-cn.com/problems/maximum-average-subarray-i