05 August 2008
给定一个由 n 个元素组成的整数数组 nums 和一个整数 k。
找到一个长度等于 k 且平均值最大的连续子数组，并返回该值。任何计算错误小于 10-5 的答案都将被接受。
prefix sum
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public double findMaxAverage(int[] nums, int k) {
if(nums.length==1)
return (double) nums[0];
double res = -Double.MAX_VALUE;
int j=0;
//Calculate and store the prefix sum in the original array itself
for(int i=1;i<nums.length; i++){
nums[i] += nums[i-1];
}
//Start at the k-1th index
//In each iteration calculate the average and slide the window right
for(int i=k-1;i<nums.length; i++){
if(i==k-1) res = Math.max((double)nums[i]/k, res);
else{
res = Math.max((double)(nums[i]-nums[j])/k, res);
j++;
}
}
return res;
}
}
two pointers sliding window
```java
class Solution {
public double findMaxAverage(int[] nums, int k) {
if (k == 0) return 0;
int max = Integer.MIN_VALUE;
int sum = 0;
int l = nums.length-k;
for(int i = 0; i < k ; i++){
sum += nums[i];
}
max = sum;
for(int left = 0, right = k; left < l && right <nums.length; left++, right++){
int nextSum = sum-nums[left]+nums[right];
max = Math.max(max, nextSum);
sum = nextSum;
}
return (double)((double)max/k);
}
}