【小红书2017年笔试】求一个数组中平均数最大的子数组
题目：
* 给一个数组，里边有N个整数，找长度为K(0<K<N)且平均值最大的子数组，并把这个最大值输出来
输入描述：
* 6 (N的值)
* 1 12 -5 -6 50 3 (含有N个整数的数组)
* 4 (K的值)
输出描述：
* 给一个数组，里边有N个整数，找长度为K(0<K<N)且平均值最大的子数组，并把这个最大值输出来
输入描述：
* 6 (N的值)
* 1 12 -5 -6 50 3 (含有N个整数的数组)
* 4 (K的值)
输出描述：
* 12.75
题目很简单，时间复杂度O(N)内解决，就是维持一个长度为K的计算窗口，遍历数组，进来后一个数则减去窗口内的第一个数，保存最大的子数组和。最后除以窗口长度转换为浮点数输出即可。
import java.util.Scanner;
public class AverageOfMaxSubArray {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = Integer.parseInt(in.nextLine());
int[] arr = new int[N];
String str = in.nextLine();
String[] str1 = str.split(" ");
for(int i=0; i<N; i++){
arr[i] = Integer.parseInt(str1[i]);
}
int K = Integer.parseInt(in.nextLine());
int sum = 0;
for(int i=0; i<K; i++){
sum += arr[i];
}
int max = sum;
for(int i=1; i<N-K; i++){
sum =sum + arr[i+K-1] - arr[i-1];
max = Math.max(sum, max);
}
System.out.println((float)max/K);
}
}运行结果：
下一篇：
面试八股文---SpringMVC