Description
You are given an integer array nums
consisting of n
elements, and an integer k
.
Find a contiguous subarray whose length is equal to k
that has the maximum average value and return this value. Any answer with a calculation error less than $10^{5}$ will be accepted.
Example 1:


Example 2:


Constraints:
n == nums.length
 1 <= k <= n <= $10^{5}$
 $10^{4}$ <= nums[i] <= $10^{4}$
Solutions
Solution 1:
Using two pointers, traverse from left to right. In the for
loop, add up K times, then compare with the maximum sum
. If it is larger, then swap, ensuring that maxSum
is always the largest subarray. After traversing, perform the average calculation for double (since double operations are more timeconsuming, the average is calculated at the end).
However, this method times out. Because the time complexity of while
+ for
is $O\left(n^2\right)$ , which leads to an excessively long traversal time.


Solution 2:
First, calculate the first subarray, and then starting from the kth element, calculate the second subarray. Here, the method of subtracting the first subarray and adding the next subarray achieves accumulation.
In this way, there is only one layer of for
loop, and the time complexity is $O\left(n\right)$

