algorithm - 为数组值的一部分求和的最佳算法

Question

A[1]给定位置, A[2], ...,中的 n 个整数数组A[n]，描述一个O(n^2)时间算法来计算A[i] + A[i+1] + … + A[j]所有的和i, j, 1 ≤ i < j ≤ n。

我尝试了多种方法来解决这个问题，但没有一个O(n^2)及时。

因此，对于包含 You 的数组{1,2,3,4} 将输出：

1+2 = 3

1+2+3 = 6

1+2+3+4 = 10

2+3 = 5

2+3+4 = 9

3+4 = 7

答案不需要使用特定的语言，首选伪代码。

标签： algorithm

Answer 1

一个好的准备就是一切。

您可以创建一个积分数组：

I[0..n] = (0, I[0] + A[1], I[1] + A[2], ..., I[n-1]+A[n]);

这将花费您O(n) * O(1)（循环所有元素并进行一次添加）；

现在你可以Sum(A, i, j)只用一个减法计算每个I[j] - I[i-1]：所以这有O(1)

i循环使用和j的所有组合1 <= (i,j) <= nhas O(n^2)。

所以你最终得到O(n) * O(1) + O(n^2) * O(1) = O(n^2).

编辑：
你的数组A从 1 开始 - 适应了这个 - 这也解决了这个小怪癖i-1 所以积分数组I从索引 0 开始并且比 1 个元素大A

编辑：