C++程序 寻找平均值最小的子数组

给定大小为n的数组arr[]和整数k，其中k <= n。

示例：

输入: arr[] = {3, 7, 90, 20, 10, 50, 40}, k = 3
输出: 索引从3到5之间的子数组
所有大小为3的子数组中，{20, 10, 50}是平均值最小的。

输入: arr[] = {3, 7, 5, 20, -10, 0, 12}, k = 2
输出: 索引在[4, 5]之间的子数组具有最小平均数

一个 简单的解决方案 是将每个元素都作为大小为k的子数组的开头，并计算以该元素开头的子数组的总和。这种解决方案的时间复杂度为O(nk)。

一种 高效的解决方案 是在O(n)时间和O(1)额外空间内解决上述问题。其思路是使用大小为k的滑动窗口。跟踪当前k个元素的总和。为了计算当前窗口的总和，请删除先前窗口的第一个元素并添加当前元素（当前窗口的最后一个元素）。

1) 初始化res_index = 0 // 结果索引的开始位置
2) 找到前k个元素的总和。将这个值记作'curr_sum'
3) 将min_sum初始化为sum
4) 从第(k+1)个元素到第n个元素，执行以下操作
   对于每个元素arr[i]，
      a) curr_sum = curr_sum + arr[i] - arr[i-k]
      b) 如果curr_sum < min_sum
           res_index = (i-k+1)
5) 打印res_index和res_index+k-1作为结果子数组的开始和结束索引。

下面是上述算法的实现。

//找到具有最小平均数的子数组的简单C++程序
#include
using namespace std;

//打印大小为k且平均值最小的子数组的开始和结束索引
void findMinAvgSubarray(int arr[], int n, int k)
{
    //k必须小于或等于n
    if (n < k)
        return;

    //初始化结果的开始索引
    int res_index = 0;

    //计算大小为k的第一个子数组的总和
    int curr_sum = 0;
    for (int i = 0; i < k; i++)
        curr_sum += arr[i];

    //将最小总和初始化为当前总和
    int min_sum = curr_sum;

    //从（k+1）'th元素到n'th元素遍历
    for (int i = k; i < n; i++) {
        //添加当前项并删除先前子数组的第一个项
        curr_sum += arr[i] - arr[i - k];

        //如有必要，更新结果
        if (curr_sum < min_sum) {
            min_sum = curr_sum;
            res_index = (i - k + 1);
        }
    }

    cout << "索引在[" << res_index << ", " << res_index + k - 1 << "]之间的子数组具有最小平均数";
}

//主程序
int main()
{
    int arr[] = { 3, 7, 90, 20, 10, 50, 40 };
    int k = 3; //子数组大小
    int n = sizeof arr / sizeof arr[0];
    findMinAvgSubarray(arr, n, k);
    return 0;
}

输出：

索引在[3, 5]之间的子数组具有最小平均数

时间复杂度：O(n)

辅助空间：O(1)