643子数组最大平均数

1
2
3

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

1
2

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

1
2
3
4
5

滑动窗口
1、维护一个长度为k的窗口，和窗口当前的和sum
2、遍历nums，每碰到一个新元素时，都要相应的从sum中减去退出窗口的值，加上新加入窗口的值
3、看看当然的sum是不是比以往的都大，是的话，记录到max里面去
4、最后返回max/k就好了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

package main

import "fmt"

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

func main() {
	nums := []int{1, 12, -5, -6, 50, 3}
	k := 4
	result := findMaxAverage(nums, k)
	fmt.Print(result)
}