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

Question

我试图找到计算数组子数组的算术平均值的方法数。
它归结为这个；给定一个数组 X 和一个整数 S，X 的多少个连续片段的算术平均值等于 S？
例如，给定 X=[5,3,6,2] 和 S=4 结果为 3。 [5,3] 、 [6,2] 和 [5,3,6,2] 的平均值为 4。

X might have up to 100.000 elements. Each value of X is an integer inrange of {-1.000.000.000,+1.000.000.000}. So is S.We don't round the arithmetic mean found.

我下面的代码(在 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

我将为此算法使用基于 1 的索引。这感觉就像是可以的情况之一。
让 P是部分和数组，即 P[0] = 0和 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 .例如， Q 中的两个值 1对应于范围 [3, 6, 2, 5]。 Q 中 0 的四个值产生六个平均范围 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 中的值范围足够小以允许计数排序。