描述；
给出一个整数数组，有正有负。找到这样一个子数组，他的长度大于等于 k，且平均值最大。
样例：
给出 nums = [1, 12, -5, -6, 50, 3], k = 3
返回 15.667 // (-6 + 50 + 3) / 3 = 15.667
思路：
平均值范围在最大值和最小值之间，采用二分法来解决，逐渐缩小最大平均值的范围。之前试过遍历每一种情况，超时了。
在代码后面做了一下具体的解释，希望我讲清楚了。
public class Solution { /** * @param nums an array with positive and negative numbers * @param k an integer * @return the maximum average */ public double maxAverage(int[] nums, int k) { // Write your code here double high = Integer.MIN_VALUE; double low = Integer.MAX_VALUE; for(int i = 0;i<nums.length;i++){ if(nums[i] > high){ high = nums[i]; } if(nums[i] < low){ low = nums[i]; } } while(high - low >= 1e-6){ double mid = (high + low)/2.0; if(search(nums , k ,mid)){ low = mid; }else{ high = mid; } } return high; } public boolean search(int[] nums , int k , double mid){ double min = 0; double[] sum = new double[nums.length + 1]; sum[0] = 0; for(int i = 1;i<=nums.length;i++){ sum[i] = sum[i - 1] + nums[i - 1] - mid; if(i>=k && sum[i] >= min){ return true; } if(i>=k){ min = Math.min(min , sum[i - k + 1]); } } return false; } }
1.一组数的平均值一定在这组数中的最大值和最小值之间。
min<=average<=max;
这组数的子数组的平均值也一定在这个范围内。
2.利用这一性质，首先求解最大值和最小值并求出它们的平均数mid。
3.用search函数判断至少k个长度的子数组的平均值与mid的大小。
search函数中计算了每一个值与mid的差，也就是和平均数之间的偏差，并依次累加求和，存贮在sum[]中。
然后比较偏差的变化，在子数组长度大于等于k之后，开始比较当前偏差之和与k个元素之前的所有偏差的最小值（以后简称最小值），如果当前偏差之和大于最小值，说明子数组的平均数被增大了，也就说明存在某一子数组的平均值大于mid，所以返回true，这样low=mid；如果遍历到最后发现偏差的和始终小于最小值，说明所有子数组的平均值，都小于mid，所以返回false，这样high=mid。
上述子数组的长度均要求大于等于k，不再强调。
所以类似于二分法，不断地确定子数组最大平均数的范围，直至high=low。
