各位题友大家好，今天是每日算法题公众号坚持日更的第 11 天。今天力扣上的每日一题是第 643 题「子数组最大平均数 I」。可以通过每日一题的小程序查看题目详情：

题目大意

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

示例

输入： [1,12,-5,-6,50,3] , k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

数据范围

  • 1 <= k <= n <= 30,000 。
  • 所给数据范围 [-10,000，10,000]。

解题思路

首先需要区分两个概念：子串（子数组）和子序列。这两个名词经常在题目中出现，非常有必要加以区分。子串sub-string（子数组 sub-array）是连续的，而子序列 subsequence 可以不连续。

方法一：preSum

今天题目让求最大平均数，由于 k 是不变的，因此可以先求区间的最大和，然后再除以 k。

上周我在题解中已经说过，求区间的和可以用 preSum。preSum 方法还能快速计算指定区间段 i ~ j 的元素之和。它的计算方法是从左向右遍历数组，当遍历到数组的 i 位置时，preSum表示 i 位置左边的元素之和。

假设数组长度为 N，我们定义一个长度为 N+1 的 preSum 数组，preSum[i] 表示该元素左边所有元素之和（不包含当前元素）。然后遍历一次数组，累加区间 [0, i) 范围内的元素，可以得到 preSum 数组。代码如下：

  1. N = len(nums)
  2. preSum = range(N + 1)
  3. for i in range(N):
  4.     preSum[i + 1] = preSum[i] + nums[i]
  5. print(preSum)

利用 preSum 数组，可以在 O(1) 的时间内快速求出 nums 任意区间 [i, j] (两端都包含) 的各元素之和。

sum(i, j) = preSum[j + 1] - preSum[i]

对于本题，可以先遍历一次，求数组每个位置的 preSum，然后再遍历一次，求长度为 k 的每个区间的最大和。最终除以 k 得到最大平均数。

643，preSum.001.jpeg

本方法的代码见下文的代码一。

方法二：滑动窗口

题目也可以抽象成长度固定为 k 的滑动窗口。当每次窗口右移的时候，需要把右边的新位置加到窗口中的和中，把左边被移除的位置从窗口的和中减掉。这样窗口里面所有元素的和是准确的，我们求出最大的和，最终除以 k 得到最大平均数。

这个方法只用遍历一次数组。

需要注意的是，需要根据 i 的位置，计算滑动窗口是否开始、是否要移除最左边元素：

  • 当 i >= k - 1 时，最左边第一个滑动窗口内的元素刚好 k 个，开始计算滑动窗口的最大和。
  • 当 i >= k 时，为了固定窗口的元素是 k 个，每次移动时需要将 i - k 位置的元素移除。

本方法的代码见下文的代码二。

代码

代码一：preSum

使用 Python2 写的代码如下。

  1. class Solution(object):
  2.     def findMaxAverage(self, nums, k):
  3.         """
  4.         :type nums: List[int]
  5.         :type k: int
  6.         :rtype: float
  7.         """
  8.         N = len(nums)
  9.         preSum = range(N + 1)
  10.         for i in range(N):
  11.             preSum[i + 1] = preSum[i] + nums[i]
  12.         largest = float("-inf")
  13.         for i in range(k - 1, N):
  14.             largest = max(preSum[i + 1] - preSum[i + 1 - k], res)
  15.         return largest / float(k)

代码二：滑动窗口

使用 Python2 写的代码如下。

  1. class Solution(object):
  2.     def findMaxAverage(self, nums, k):
  3.         """
  4.         :type nums: List[int]
  5.         :type k: int
  6.         :rtype: float
  7.         """
  8.         sums = 0
  9.         largest = float('-inf')
  10.         for i, num in enumerate(nums):
  11.             sums += num
  12.             if i >= k:
  13.                 sums -= nums[i - k]
  14.             if i >= k - 1:
  15.                 largest = max(sums, largest)
  16.         return largest / float(k)

刷题心得

今天的题目非常好，虽然是个 Easy 题目，但是让我们练习了 preSum 和 滑动窗口 两种方法的最基本用法。

  • preSum 方法要注意定义的 preSum 是否包含当前元素；
  • 滑动窗口 方法要注意窗口的大小要固定为 k。

欢迎加入刷题群

目前已经近 2000 人加入了每日一题打卡群。加入方式是通过每日一题打卡网站。每天都会同步力扣每日一题，这是个互相帮助、互相监督的算法题打卡网站，其地址是 https://www.ojeveryday.com/
【每日一题】643. 子数组最大平均数 I - 图2

想加入千人刷题群的朋友，可以复制上面的链接到浏览器，然后在左侧点击「加入组织」，提交力扣个人主页，即可进入刷题群。期待你早日加入。

也可点击 「阅读原文」，直接提交力扣个人主页。

关于作者

我是本文的作者是负雪明烛，毕业于北京邮电大学，目前就职于阿里巴巴。坚持刷算法题 5 年，共计刷了 800 多道算法题。做过的每个算法题都在 CSDN 上写题解博客，获得好评无数，CSDN 的累计阅读量已经 160万 次！博客地址是：https://blog.csdn.net/fuxuemingzhu
「每日算法题」公众号是我维护的一个算法题解公众号，主要讲解算法题的解法，也会分享找工作的经验。欢迎关注。
【每日一题】643. 子数组最大平均数 I - 图3

题目来源：643. 子数组最大平均数 I
链接：https://leetcode-cn.com/problems/maximum-average-subarray-i