algorithm - 查找给定数组中 L 到 R 范围内的值

Question

给定数组A，以及两个索引L和R，求出

的值

Summation(AS[i]*AS[j]*AS[k])

哪里L<=i<j<k<=R成立，并且AS是 A 的所有元素的排序集在范围内 L至R包容性。

示例: 让A=(4,4,1,6,1,3) L=0和R=3给出AS=(1,4,6) ，所以Ans=1*4*6=24

我没有任何比 O(n^3) 更好的方法，它非常慢。 请建议我一些更快的方法。

A 中的元素数量最多为 10^5。

Answer 1

正如问题评论员所说，确定AS可以通过使用哈希表 H 来完成。您只需迭代 A 的元素即可来自索引 L至R然后将每个元素插入 H 。结果应该是您需要的元素集。您仍然需要对集合进行排序。为此，您可以复制 H 的元素放入一个数组并对该数组进行排序。结果是AS 。这应该不超过 O(NlogN)步骤，其中 N=R-L .

评论员没有说的是如何有效地计算总和。可以在O(N)中完成脚步。方法如下。

我们首先进行以​​下观察:

Sum(AS[j]*AS[k], a <= j < k <= b) = 
   1/2*(AS[a] + AS[a+1] + ... + AS[b])^2 - 
   1/2*(AS[a]^2 + AS[a+1]^2 + ... + AS[b]^2)

我们将目标金额扩大如下:

S = Sum(AS[i]*AS[j]*AS[k]) = 
   AS[L]   * Sum(AS[j]*AS[k], L+1 <= j < k <= R) +     (iteration     1)
   AS[L+1] * Sum(AS[j]*AS[k], L+2 <= j < k <= R) +     (iteration     2)
   ...
   AS[R-2] * Sum(AS[j]*AS[k], R-1 <= j < k <= R).      (iteration R-L-1)

我们现在应用观察结果。

确定 Sum(AS[j]*AS[k], a <= j < k <= b) 形式的总和我们可以首先有效地计算

S1 = AS[L] + AS[L+1] + ... + A[R]
S2 = AS[L]^2 + AS[L+1]^2 + ... + A[R]^2

然后，当我们迭代 AS 的元素时，从每个总和中逐渐减去第一项来自索引 L至R-2 .

因此，可以在O(N)中确定您想要的总和。确定 AS 后的步骤。假设您使用某种比较排序方法，整个算法应采用 O(|A|) + O(NlogN) + O(N)步骤。