LeetCode 75 - 643. Maximum Average Subarray I

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:

1
2
3
Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Example 2:

1
2
Input: nums = [5], k = 1
Output: 5.00000

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 time-consuming, 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int left{0};
        int right{k};
        int maxSum = INT_MIN;
        int sum{};
        while (right <= nums.size()) {
            for (int i = left; i < left + k; ++i) {
                sum += nums[i];
            }

            if (sum > maxSum)
                maxSum = sum;

            left++;
            right++;
            sum = 0;
        }
        return static_cast<double>(maxSum) / k;
    }
};

Solution 2:

First, calculate the first subarray, and then starting from the k-th 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)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int sum = 0;
        int n = nums.size();
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int maxSum = sum;
        for (int i = k; i < n; i++) {
            sum = sum - nums[i - k] + nums[i];
            maxSum = max(maxSum, sum);
        }
        return static_cast<double>(maxSum) / k;
    }
};