如何比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，我们有两种可能性：

a(1) 两个平均值相等，在这种情况下，整个子数组的平均值与和相同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) 

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

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