What is the sliding window approach?

The sliding window approach involves maintaining a fixed-size window over the array, efficiently updating the sum or other calculations as the window slides across the array.

How can I solve the Maximum Average Subarray I problem more efficiently?

Use the sliding window technique to maintain a running sum of the current subarray, updating it as the window slides across the array. This ensures linear time complexity.

Why is the space complexity O(1) in this solution?

The space complexity is O(1) because we only need a few variables to track the current sum and maximum average, and do not require additional data structures.

What happens if k equals the length of the array?

If k equals the length of the array, the only possible subarray is the entire array, and the solution simply computes its average.

Can this approach be extended to other problems?

Yes, the sliding window technique is widely applicable to array problems, including finding maximum sums or products of subarrays, or solving dynamic problems with varying window sizes.

#643

Easy

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。请你找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。任何误差小于 10 -5 的答案都将被视为正确答案。示例 1：输入： nums = [1,12,-5,-6,50,3], k = 4 输出： 12.75 解释…

数组滑动窗口

题目描述

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10^-5 的答案都将被视为正确答案。

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

输入：nums = [5], k = 1
输出：5.00000

提示：

n == nums.length
1 <= k <= n <= 10⁵
-10⁴ <= nums[i] <= 10⁴

lightbulb

解题思路

方法一：滑动窗口

我们维护一个长度为 $k$ 的滑动窗口，每次计算窗口内的和 $s$ ，取最大的和 $s$ 作为答案。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        ans = s = sum(nums[:k])
        for i in range(k, len(nums)):
            s += nums[i] - nums[i - k]
            ans = max(ans, s)
        return ans / k

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates should understand how to implement the sliding window technique and avoid brute force solutions.
question_mark
Look for an understanding of maintaining a running sum efficiently during window shifts.
question_mark
Candidates who are familiar with space optimization techniques and avoid unnecessary data structures will perform well.

warning

常见陷阱

外企场景

error
Candidates may incorrectly compute the sum after sliding the window, resulting in incorrect averages.
error
Misunderstanding the sliding window approach could lead to a brute-force solution with O(n*k) complexity.
error
Candidates might forget to handle small edge cases such as when the array has only one element.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider using a sliding window for other array problems, like finding the maximum sum of subarrays.
arrow_right_alt
What if k was dynamic? How would you adjust the sliding window approach to accommodate varying subarray sizes?
arrow_right_alt
Extend the solution to find the subarray with the maximum product instead of the sum.

help

常见问题

外企场景

继续练习

#632 最小区间 #658 找到 K 个最接近的元素 #689 三个无重叠子数组的最大和