如何计算最小平均子数组的时间复杂度优于O(n^2)？

Question

我编写了以下代码，用于计算子数组（至少两个元素）平均值最小的最小起始索引。

但是，我无法想出一种更快的方法，即O(n)或O(n log n)的方法。我无法想到任何遍历所有可能的子数组且时间复杂度不超过O(n^2)的方式：

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

int solution(vector<int> &A) {
    float previousAvg = 0.0;
    float minAvg = numeric_limits<float>::max();
    int minStartIx = numeric_limits<int>::max();
    for (size_t i = 0; i < A.size(); ++i) {
        for (size_t j = i + 1; j < A.size(); ++j) {
            if (j == i + 1) {
                previousAvg = (A[i] + A[j]) / 2.0;
                cout << "avg(from=" << i << ", to=" << j << ") = " << previousAvg << endl;
            } else {
                previousAvg = (previousAvg * (j - i) + A[j]) / (j - i + 1);
                cout << "avg(from=" << i << ", to=" << j << ") = " << previousAvg << endl;
            }
            if (previousAvg < minAvg) {
                minAvg = previousAvg;
                minStartIx = i;
            }
        }
    }
    return minStartIx;
}

int main() {
    vector<int> A = {4, 2, 2, 5, 1, 5, 8};
    cout << solution(A) << " must equal to 1" << endl;
    return 0;
}

并且在记录日志的情况下，它生成了正确的输出：

avg(from=0, to=1) = 3
avg(from=0, to=2) = 2.66667
avg(from=0, to=3) = 3.25
avg(from=0, to=4) = 2.8
avg(from=0, to=5) = 3.16667
avg(from=0, to=6) = 3.85714
avg(from=1, to=2) = 2
avg(from=1, to=3) = 3
avg(from=1, to=4) = 2.5
avg(from=1, to=5) = 3
avg(from=1, to=6) = 3.83333
avg(from=2, to=3) = 3.5
avg(from=2, to=4) = 2.66667
avg(from=2, to=5) = 3.25
avg(from=2, to=6) = 4.2
avg(from=3, to=4) = 3
avg(from=3, to=5) = 3.66667
avg(from=3, to=6) = 4.75
avg(from=4, to=5) = 3
avg(from=4, to=6) = 4.66667
avg(from=5, to=6) = 6.5
1 must equal to 1

- SkyWalker

---

有很多解决问题的方法，我怀疑你没有学过其中任何一种。请说明你所想到的方法，也许我们可以从那里开始着手。 - Passer By

@UmNyobe 你的意思是这是一个伪装成DP的东西吗？ - SkyWalker

Bingo，这其实是动态规划的伪装。 - UmNyobe

也许更适合 [computerscience.se]？ - L. F.

Answer 1

参考这里，我试着总结自己的理解。

如果我们将一个（连续的）子数组分成两个部分，其中一个部分的平均值为a，长度为n，另一个部分的平均值为b，长度为m，我们有两种可能：

（1）两个平均值相等，此时整个子数组的平均值与a和b相同：

  (an + bm) / (n + m)
= (an + am) / (n + m) (a equals b)
= a(n + m) / (n + m)
= a
= b

(2) 其中一个平均数小于另一个平均数，此时它也小于整个子数组的平均数：

(Averages a and b)
a < b
(an + bm) / (n + m) > a (the average of the whole is greater than a's)
an + bm > a(n + m)
an + bm > an + am (since b > a) 

现在想象一下，我们正在查看具有最小平均值且具有三个以上元素的子数组之一。当部分具有相等平均值时，递归地拆分每个部分; 根据上面的逻辑，部分必须具有相等的平均值，否则我们将产生矛盾，因为我们假设整个子数组的平均值是最小的。最终，我们将找到有两个或三个元素的子数组。由于我们从具有最小平均值的（较大的）子数组开始，所以两个或三个元素的子数组组件也必须具有相同的最小平均值。

这证明了我们需要检查的最大窗口是三个元素。最小的窗口是两个元素，因为那是我们的最小长度。O（n）。

- גלעד ברקן