子数组最大平均数 I 图解题解

这道题到底在问什么

输入

nums = [1,12,-5,-6,50,3], k = 4

输出

12.75（下标 1~4 的 [12,-5,-6,50] 之和 51，51/4=12.75）

最优解：一步一步想明白

1. 3核心就一句：窗口右移一格 = 加新进的、减滑出的。和是边滑边更新的，全程只扫一遍。
2. 4先搭起始窗口：把下标 0 到 0 的数加起来，目前窗口和是 1。继续往右凑够 k 个。
3. 5先搭起始窗口：把下标 0 到 1 的数加起来，目前窗口和是 13。继续往右凑够 k 个。
4. 6先搭起始窗口：把下标 0 到 2 的数加起来，目前窗口和是 8。继续往右凑够 k 个。
5. 7先搭起始窗口：把下标 0 到 3 的数加起来，目前窗口和是 2。前 k 个数凑齐了。
6. 8起始窗口（高亮这 k 个）的和是 2，先把它当成目前见过的最大窗口和。接下来窗口开始向右滑。
7. 9窗口准备向右滑一格。标红的下标 0（值 1）马上要滑出窗口，绿色的下标 4（值 50）马上要进窗口。
8. 10窗口滑到下标 1~4。新和 = 旧和 2 + 进的 50 − 出的 1 = 51。这比之前的最大还大，记下它。
9. 11窗口准备向右滑一格。标红的下标 1（值 12）马上要滑出窗口，绿色的下标 5（值 3）马上要进窗口。
10. 12窗口滑到下标 2~5。新和 = 旧和 51 + 进的 3 − 出的 12 = 42。没超过当前最大 51，最大值不变。
11. 13窗口准备向右滑一格。标红的下标 2（值 -5）马上要滑出窗口，绿色的下标 6（值 -2）马上要进窗口。
12. 14窗口滑到下标 3~6。新和 = 旧和 42 + 进的 -2 − 出的 -5 = 45。没超过当前最大 51，最大值不变。
13. 15窗口准备向右滑一格。标红的下标 3（值 -6）马上要滑出窗口，绿色的下标 7（值 7）马上要进窗口。
14. 16窗口滑到下标 4~7。新和 = 旧和 45 + 进的 7 − 出的 -6 = 58。这比之前的最大还大，记下它。
15. 17窗口准备向右滑一格。标红的下标 4（值 50）马上要滑出窗口，绿色的下标 8（值 4）马上要进窗口。
16. 18窗口滑到下标 5~8。新和 = 旧和 58 + 进的 4 − 出的 50 = 12。没超过当前最大 58，最大值不变。
17. 19窗口准备向右滑一格。标红的下标 5（值 3）马上要滑出窗口，绿色的下标 9（值 -1）马上要进窗口。
18. 20窗口滑到下标 6~9。新和 = 旧和 12 + 进的 -1 − 出的 3 = 8。没超过当前最大 58，最大值不变。
19. 21窗口准备向右滑一格。标红的下标 6（值 -2）马上要滑出窗口，绿色的下标 10（值 8）马上要进窗口。
20. 22窗口滑到下标 7~10。新和 = 旧和 8 + 进的 8 − 出的 -2 = 18。没超过当前最大 58，最大值不变。
21. 23窗口准备向右滑一格。标红的下标 7（值 7）马上要滑出窗口，绿色的下标 11（值 2）马上要进窗口。
22. 24窗口滑到下标 8~11。新和 = 旧和 18 + 进的 2 − 出的 7 = 13。没超过当前最大 58，最大值不变。
23. 25滑完整趟，所有长度 4 的窗口里和最大的是高亮这一段（和 58）。最大平均 = 58 ÷ 4 = 14.5，就是答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

def findMaxAverage(nums, k):
    s = sum(nums[:k])          # 起始窗口和
    best = s
    for r in range(k, len(nums)):
        s += nums[r] - nums[r-k]  # 加新进的、减滑出的
        best = max(best, s)
    return best / k

double findMaxAverage(vector<int>& nums, int k){
    int s = 0;
    for (int i = 0; i < k; i++) s += nums[i];
    int best = s;
    for (int r = k; r < nums.size(); r++) {
        s += nums[r] - nums[r-k];
        best = max(best, s);
    }
    return (double)best / k;
}

public double findMaxAverage(int[] nums, int k) {
    int s = 0;
    for (int i = 0; i < k; i++) s += nums[i];
    int best = s;
    for (int r = k; r < nums.length; r++) {
        s += nums[r] - nums[r-k];
        best = Math.max(best, s);
    }
    return (double) best / k;
}

复杂度

面试官可能追问