在数组中有效地找到子数组的算术平均值

Question

我试图找到计算数组子数组的算术平均值的方法数。它归结为这个；给定一个数组 X 和一个整数 S，X 的多少个连续片段的算术平均值等于 S？

例如，给定 X=[5,3,6,2] 和 S=4 结果为 3。 [5,3] 、 [6,2] 和 [5,3,6,2] 的平均值为 4。

X 可能有多达 100.000 个元素。X 的每个值都是 {-1.000.000.000,+1.000.000.000} 范围内的整数。S 也是如此。我们不对找到的算术平均值进行四舍五入。

我下面的代码（在 Java 上）适用于小数据集，但效率不高。O(n^2)。

public static int returnSubsequenceCount(int[] X, int S) {
        int counter = 0;

        for (int i = 0; i < X.length; i++) {
            int[] dpSum = new int[X.length];

            dpSum[i] = X[i];

            if (X[i] == S) {
                counter++;
            }

            for (int j = i + 1; j < X.length; j++) {
                int sum = dpSum[j - 1] + X[j];

                dpSum[j] = sum;

                if ((double) sum / (j - i + 1) == S) {
                    counter++;
                }
            }
        }
        return counter;
    }

Answer 1

这里有一个获取O(n)算法的技巧：

average = (A[i] + A[i+1] ... + A[j]) / (j - i + 1)

average * (j - i + 1) = A[i] + A[i+1]...+ A[j]

请注意，由于average现在正好乘以等式右侧的元素数量，因此我们可以为每个元素减去一次平均值：

0 = (A[i]-average) + (A[i+1]-average) ... + (A[j]-average)

可以通过检查前缀和来查找等于零的连续和。对于每个最右边的元素 ( A[j]-average)，我们想要添加我们之前看到的相同前缀和的次数。我们对前缀和 0 进行调整，以便计算数组前缀的全长（如果适用）：

2 1 3, avg 2

2-2 = 0    ps = 0    count = 1 (1 for the full array prefix)
1-2 = -1   ps = -1
3-2 = 1    ps = 0    count = 2 (1 for index 0 and 1 for the full array prefix)

                     total = 3

Answer 2

我将为此算法使用基于 1 的索引。这感觉就像是可以的情况之一。

让P是部分 sums 数组，即P[0] = 0and P[i] = X[1] + ... + X[i]。此外，让Q[i] = P[i] - S * i. 例如，

i     0   1   2   3   4   5   6   7
-----------------------------------
X         5   3   6   2   5   5   2
P     0   5   8  14  16  21  26  28
Q     0   1   0   2   0   1   2   0

[i,j]（包括i和j）的平均值是什么意思S？有了上面的记号，可以写成

(P[j] - P[i - 1]) / (j - i + 1) = S     ==>
P[j] - P[i - 1] = S * (j - i + 1)       ==>
P[j] - P[i - 1] = S * j - S * (i - 1)   ==>
P[j] - S * j = P[i - 1] - S * (i - 1)   ==>
Q[j] = Q[i - 1]

这意味着任何一对相等的值都Q对应于一个平均值的范围S。例如，1 中的两个值Q对应于范围 [3, 6, 2, 5]。0 的四个值Q产生六个平均值范围S=4：[5,3], [6,2], [5,5,2], [5,3,6,2], [6,2,5 ,5,2] 和 [5,3,6,2,5,5,2]。

因此，以下算法也在 中运行O(n log n)，与@Polygnome 的注释相同，但应该更容易实现：

• 计算Q；
• 排序 Q;
• 对于 中的每批k相等值Q，添加k * (k - 1) / 2到答案中；
• 返回答案。

这可以简化为O(n)使用哈希表，或者如果值的范围Q足够小以允许计数排序。