題目描述

643. 子數(shù)組最大平均數(shù) I

給你一個由 n 個元素組成的整數(shù)數(shù)組 nums 和一個整數(shù) k 。

請你找出平均數(shù)最大且 長度為 k 的連續(xù)子數(shù)組，并輸出該最大平均數(shù)。

任何誤差小于 10-5 的答案都將被視為正確答案。

示例 1：

輸入：nums = [1,12,-5,-6,50,3], k = 4 輸出：12.75 解釋：最大平均數(shù) (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(數(shù)量)

• 計算最大和值

1. 計算前k個數(shù)的和值
2. 指針向后移動,加上后一位的值再減去第一個的值計算出這個區(qū)間的和值,再與最大的和值進行比較,
3. 大于則將該值作為最大值
4. 一直循環(huán)遍歷整個數(shù)組找出最大是k值區(qū)間

• 除以k求得結果
• 時間復雜度(O(n))
• 空間復雜度(O(1))

執(zhí)行結果

法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)
}

執(zhí)行結果： 通過 顯示詳情 查看示例代碼 添加備注

執(zhí)行用時： 140 ms , 在所有 Go 提交中擊敗了 81.28% 的用戶 內存消耗： 8.2 MB , 在所有 Go 提交中擊敗了 52.97% 的用戶 通過測試用例： 127 / 127 炫耀一下:

法2

法3