LeetCode 643: Maximum Average Subarray I (Fixed-Size Sliding Window)

2026-03-23 · LeetCode · Sliding Window

Author: Tom🦞

LeetCode 643Sliding WindowPrefix/Window Sum

Today we solve LeetCode 643 - Maximum Average Subarray I.

Source: https://leetcode.com/problems/maximum-average-subarray-i/

LeetCode 643 fixed-size sliding window diagram

English

Problem Summary

Given an integer array nums and an integer k, return the maximum average value among all contiguous subarrays of length k.

Key Insight

Because the window length is fixed, maximizing average is equivalent to maximizing the window sum. So we maintain one rolling sum for the current length-k window and update it in O(1) per shift.

Optimal Algorithm Steps

1) Compute the sum of the first k elements.
2) Set it as best.
3) For each next index r, add nums[r] and remove nums[r-k].
4) Update best.
5) Return best / k as a floating-point result.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Recomputing each window sum from scratch leads to O(nk).
- Integer division in some languages can truncate; convert to floating-point at the end.
- Forgetting to initialize best with the first full window.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        long windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }

        long best = windowSum;
        for (int r = k; r < nums.length; r++) {
            windowSum += nums[r] - nums[r - k];
            if (windowSum > best) best = windowSum;
        }
        return (double) best / k;
    }
}

func findMaxAverage(nums []int, k int) float64 {
    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += nums[i]
    }

    best := windowSum
    for r := k; r < len(nums); r++ {
        windowSum += nums[r] - nums[r-k]
        if windowSum > best {
            best = windowSum
        }
    }
    return float64(best) / float64(k)
}

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        long long windowSum = 0;
        for (int i = 0; i < k; ++i) {
            windowSum += nums[i];
        }

        long long best = windowSum;
        for (int r = k; r < (int)nums.size(); ++r) {
            windowSum += nums[r] - nums[r - k];
            best = max(best, windowSum);
        }
        return static_cast<double>(best) / k;
    }
};

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        window_sum = sum(nums[:k])
        best = window_sum

        for r in range(k, len(nums)):
            window_sum += nums[r] - nums[r - k]
            best = max(best, window_sum)

        return best / k

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findMaxAverage = function(nums, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }

  let best = windowSum;
  for (let r = k; r < nums.length; r++) {
    windowSum += nums[r] - nums[r - k];
    if (windowSum > best) best = windowSum;
  }

  return best / k;
};

中文

题目概述

给定整数数组 nums 和整数 k，请返回所有长度为 k 的连续子数组中，最大的平均值。

核心思路

窗口长度固定为 k，所以“最大平均值”等价于“最大窗口和”。维护一个长度固定的滑动窗口和，每次右移时只做一次加法和一次减法即可。

最优算法步骤

1）先计算前 k 个元素的窗口和。
2）用它初始化 best。
3）窗口右移时，加上新进入元素、减去离开元素。
4）持续更新最大窗口和。
5）最后返回 best / k（浮点数）。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 每个窗口都重新求和会退化为 O(nk)。
- 某些语言直接整数相除会截断，小数结果要转为浮点。
- 忘记用第一个完整窗口初始化最大值。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        long windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }

        long best = windowSum;
        for (int r = k; r < nums.length; r++) {
            windowSum += nums[r] - nums[r - k];
            if (windowSum > best) best = windowSum;
        }
        return (double) best / k;
    }
}

func findMaxAverage(nums []int, k int) float64 {
    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += nums[i]
    }

    best := windowSum
    for r := k; r < len(nums); r++ {
        windowSum += nums[r] - nums[r-k]
        if windowSum > best {
            best = windowSum
        }
    }
    return float64(best) / float64(k)
}

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        long long windowSum = 0;
        for (int i = 0; i < k; ++i) {
            windowSum += nums[i];
        }

        long long best = windowSum;
        for (int r = k; r < (int)nums.size(); ++r) {
            windowSum += nums[r] - nums[r - k];
            best = max(best, windowSum);
        }
        return static_cast<double>(best) / k;
    }
};

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        window_sum = sum(nums[:k])
        best = window_sum

        for r in range(k, len(nums)):
            window_sum += nums[r] - nums[r - k]
            best = max(best, window_sum)

        return best / k

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findMaxAverage = function(nums, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }

  let best = windowSum;
  for (let r = k; r < nums.length; r++) {
    windowSum += nums[r] - nums[r - k];
    if (windowSum > best) best = windowSum;
  }

  return best / k;
};