Description:

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4Output: 12.75Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

1 <= k <= n <= 30,000.Elements of the given array will be in the range [-10,000, 10,000].

My Solution:

class Solution {    public double findMaxAverage(int[] nums, int k) {       int max = Integer.MIN_VALUE;       int len = nums.length;       int temp = 0;       if(len == k){            for(int num : nums){                temp += num;            }           return (temp * 1.0)/k;        }        for(int i = 0;i <= len - k;i++){            temp = 0;            for(int j = i;j < i + k;j++){                temp += nums[j];            }            if(temp > max){                max = temp;            }        }        return (max * 1.0) / k;    }}

Better Solution1:

//sum[i]存储的是nums前i+1个元素之和//sum[i] -sum[i - k]表示以i为最后一个元素，k个元素之和public class Solution {    public double findMaxAverage(int[] nums, int k) {        int[] sum = new int[nums.length];        sum[0] = nums[0];        for (int i = 1; i < nums.length; i++)        sum[i] = sum[i - 1] + nums[i];        double res = sum[k - 1] * 1.0 / k;        for (int i = k; i < nums.length; i++) {            res = Math.max(res, (sum[i] - sum[i - k]) * 1.0 / k);        }        return res;    }}

Better Solution2:

public class Solution {//先计算出0开始的前k个元素之和,由于nums[1]+nums[2]...nums[k]= nums[0]+nums[1]+...nums[k - 1]+nums[k] - nums[0],利用这个公式一直以nums[i]为最后一个元素滑动    public double findMaxAverage(int[] nums, int k) {        double sum=0;        for(int i=0;i