【LeetCode】Python实现-643. 子数组最大平均数 I

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

示例 1:
输入: [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]。

我的解答：

class Solution(object):
    def findMaxAverage(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: float
        """
        s = -10000*30000
        n = 0
        if k == len(nums):
            return sum(nums[:])/float(k)
        for i in range(len(nums)-k+1):
            n = sum(nums[i:i+k])
            if n > s:
                s = n
        return s/float(k)
        

分别计算相邻k个元素的和，找出最大值，思路简单，但是执行速度特别慢。

别人的解答：（执行用时为 116 ms 的范例）

class Solution(object):
    def findMaxAverage(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: float
        """
        m=f=sum(nums[0:k])
        for i in range(0,len(nums)-k):
            f+=nums[i+k]-nums[i]
            if f>m:
                m=f
        return m*1.0/k

这种解法的思路如下图所示，将每一次的求和运算转化为了两个数的算术运算，减少了执行时间。