如何计算出比 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

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）。