寻找任意子数组中所有元素之和的最佳算法是什么？

Question

寻找任意子数组中所有元素之和的最佳算法是什么？

6

我有一个问题，以及一个还算可以的解决方案。我希望能找到更好的解决方案。

问题

我有一个包含约200,000个整数的数组。给定两个索引i1和i2，我需要计算i1和i2之间所有元素的总和。数组中的每个整数都在1到4之间（包括1和4）。例如：

a = [1, 3, 2, 4, 3, 2, 4, 1];
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2)

这个操作需要执行大约200,000次，所以需要足够快。在for循环中使用简单的计数器是O(n)，速度太慢了。数组在构建后永远不会被修改，因此具有相对昂贵的预处理阶段是可以接受的。

我目前最好的解决方案是：

该算法的时间复杂度为O(log n)：

首先用零填充原始数组，直到其长度为2的幂。然后将数组分成两个相等的部分并存储每个部分的和。然后将数组分成四分之一并存储每个部分的和。然后是八分之一，一直重复这样做，直到将数组拆分为长度为2的部分。对于上面的8个元素的数组，这需要进行两个步骤。

halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])]
quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])]

现在，给定两个索引，可以在O(log n)的时间内计算出子段和。例如，subsection_sum(a, 2, 7) == quarters[1] + halves[1]。

- Bernie Sumption

2个回答

4

如果你能承受O(n)的额外存储空间，你可以创建一个查找表，其中第i个元素是输入数组中索引0到i（包括）处元素的总和。伪代码如下：

def computeLookupTable(arr):
    let n = arr.length
    let lookupTable = new Array()

    lookupTable[0] = arr[0]

    for i=1 to n:
        lookupTable[i] = arr[i] + lookupTable[i-1]

    return lookupTable

接下来，你可以使用这个表格来计算在i1和i2之间的array数组中所有元素的总和，方法是取差值。

lookupTable[i2] - lookupTable[i1]

这需要恒定的时间。

- Matt Ball

3

我会说我们提供了很好的互补解释。 - Michael J. Barber

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michael J. Barber · Accepted Answer

引入一个辅助数组，其中包含累加和。即，辅助数组的第i个元素具有原始数组从0到i元素的总和。那么子数组的总和就是从辅助数组中两个元素之差。这将在常数时间O(1)内给出结果。

这取决于问题中给出的subsection_sum函数中的不变量：

subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1) + subsection_sum(a, i1, i2)

我假设 i1 <= i2。重新排列得到：

subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1)

请注意右侧的求和都从0开始。辅助数组可以被视为缓存所有i的零到subsection_sum(a, 0, i)之和的值。