給你一個長度為n的整數陣列，以及一個整數k。試著從中找出長度為k的子陣列，讓他可以擁有最大的平均值。

Solution

var findMaxAverage = function(nums, k) {
    // Get the first max
    let sum = 0;
    for (let i = 0; i < k; i++) {
        sum += nums[i];
    }

    let maxSum = sum;

    for (let j = k; j < nums.length; j++) {
        // Moving Window
        // Remove first element
        // Add last element
        sum = sum - nums[j - k] + nums[j];
        maxSum = Math.max(maxSum, sum);
    }

    return 1.0 * maxSum / k;
};

檢討

• 這題考你Sliding Window類型的演算法

我們首先計算前k個數字的總和，把他視為maxSum的初始值

 0  1   2   3   4   5
[1, 12, -5, -6, 50, 3]
 |  ---  |    
 ^       ^

            j # 從這裡開始準備滑動
#假設k=3
maxSum = sum(nums[0:3])

接下來我們把次一個指標的初始值設定為k，準備從這邊開始滑動視窗
一但滑動，我們的sum就會跟著發生改變:
- 必須扣除第j-k個元素的數值
- 同時加上第j個元素的值

接下來一路不停的更新MaxSum到整個陣列走訪完畢。