[Leetcode] 643. Maximum Average Subarray I

643. Maximum Average Subarray I

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 = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

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

easy难度的，应该没啥弯弯绕。但是有一点，要问清楚每个数字大小，数组有多少数字。确保1. 每个数字不overflow了Max int
2. 他们的和不overflow了Max int
如果数字太大， 就要用string 求和的方法了。鉴于这道题是easy，题目给的note里就有限制了，所以这道题我们不用担心。

尝试了一格一格挪，每次取k个数加起来的最原始办法， 复杂度应该是nk果然超时了TLE。。。就在用这个原始方法的时候，也出了问题了，我在for循环里的limit是nums.length-k，实际上应该是nums.length-k+1. 然鹅，事实是这个样子滴，在我们单独讲循环某个数组的时候，limit应该是小于这个数组的长度，因为等于长度就读不出来数了，当从0开始算index的时候。

但是向这类的移动平均值呢，这个limit的物理意义是，我们要移动多少下。不举具体数字栗子，就干想我们有一个数组，长度是n，要取window长度为k的平均值。我们把长度为n的数组和长度为k的数组上下摞起来，多出来的就是n-k。但是！我们并不能设置limit为n-k，因为，这样我们就少移动了一次，最后一个k的window我们没有读到！


好吧，第二招，稍微不那么笨的，就是把当前算好的减去第一个数，加上向后挪一个的数。喜大普奔啊，代码两次就过了，而且击败了全球83%。好像是目前的最好战绩了呢！大神们请绕路。。。再绕回来然后，欢迎大神指点啊，本渣感激不尽！

通过这个easy的小题目呢，我们明白了一个道理：
1. for循环物理意义是次数，在这里就是移动的次数；
2. 不用管for 的int i 起始k是啥，（i<,用小于号的时候）循环的次数等于limit-k；
3. 这个window每个里面有k个数值，首尾相隔k-1个数。所以每次计算减掉上次求和数组前面的一个数，在加上当前的数，中间相隔k个数；
4. 那么问题来了，既然for循环是看移动的次数，那么，我们说好的移动n-k+1次移动，怎么limit是n，起点是k，那不就是n-k了？lol。。。聪明的你想到答案了吗？
答案见最下边。




AC Solution:

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        // The number has a limit, which all the sum max will not exceed max int
        double lastSum = 0;
        for(int i=0; i<k; i++){
            lastSum += nums[i];
        }
        double maxAvg = lastSum/k;
        for(int i=k; i<nums.length; i++){
            double curSum = 0;
            curSum = lastSum-nums[i-k]+nums[i];
            maxAvg = Math.max(maxAvg, curSum/k);
            lastSum = curSum;
        }
        return maxAvg;
    }
}

答案：我们计算初始maxAvg的时候算过一次啊！捂脸哭，我卡着卡了好久，百思不得其解。。。蠢哭