leetcode 643. 子数组最大平均数 I

leetcode 643. 子数组最大平均数 I

题目描述

643. 子数组最大平均数 I

给你一个由 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

提示：

n == nums.length 1 <= k <= n <= 105 -104 <= nums[i] <= 104

解题思路

法1

方法1:滑窗

我们需要得到最大的和值然后再除以k(数量)

• 计算最大和值

1. 计算前k个数的和值
2. 指针向后移动,加上后一位的值再减去第一个的值计算出这个区间的和值,再与最大的和值进行比较,
3. 大于则将该值作为最大值
4. 一直循环遍历整个数组找出最大是k值区间

• 除以k求得结果
• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

func findMaxAverage(nums []int, k int) float64 {
 t := 0
 for i := 0; i < k; i++ {
  t += nums[i]
 }
 r := t
 for i := k; i < len(nums); i++ {
  t = t - nums[i-k] + nums[i]
  if t > r {
   r = t
  }
 }
 return float64(r) / float64(k)
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 140 ms , 在所有 Go 提交中击败了 81.28% 的用户 内存消耗： 8.2 MB , 在所有 Go 提交中击败了 52.97% 的用户 通过测试用例： 127 / 127 炫耀一下:

法2

法3