好久没有刷LeetCode了，准备重拾并坚持下去，每天刷个两小时。今天算是开始的第一天，不过出师不利，在一道很简单的题目上墨迹半天。不过还好，现在踩过的坑，应该都不会白踩，这些可能都是以后程序员路上稳固的基石哦。任何优秀的程序员不都是这样过来的嘛，坚持就好。
注意：大家练习时同样要注意代码的风格，这一点推荐上lintcode测试一下，练习几次风格自然就好了。
下面开始写第一题的解题过程（包括写错的过程）
思路一：累加数组
1. 求出数组的累加数组(循环遍历，每一项等于前一项的和)
2. k个数的和等于 i 位置上的数减去 i - k 位置上的数（对于坐标比较迷糊的同学，推荐你们在稿纸上画画就明白了）。
第一遍错误的代码（黄色标记处错误）：
public class Solution {
public double findMaxAverage(int[] nums, int k) {
if (nums == null || nums.length < 1) {
return -1;
}
int[] ans = new int[nums.length];
double maxSum = 0;
ans[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
ans[i] = nums[i] + nums[i - 1];
}
maxSum = ans[k - 1];
for (int i = k; i < nums.length; i++) {
double curSum = (double)ans[i] - ans[i - k];
if (curSum > maxSum) {
maxSum = curSum;
}else {
continue;
}
}
return maxSum / k;
}
}
nums改成ans就正确了。
时间复杂度：O(n)只是两遍遍历，没有嵌套。
空间复杂度：O(n)申请了一个数组
思路二：滑动窗口
维护一个“和”数组，只有k个元素，从k+1开始，每次右边加一个元素，左边减一个元素。
相比一的好处：不用申请数组了，而且效率也高了，减少了重复计算。
这次终于BugFree了，不容易啊。
public class Solution {
public double findMaxAverage(int[] nums, int k) {
if (nums.length < 1 || nums == null) {
return -1;
}
int sum = 0;
int max = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];// 先求前k个数的和，之后不断维护这个数组即可。
max = sum;
}
for (int i = k; i < nums.length; i++) {
sum += nums[i] - nums[i - k];
if (sum > max) {
max = sum;
}
}
return max * 1.0 / k;
}
}
时间复杂度：O(n)只是遍历一遍
空间复杂度：O(1)