寻找任意子阵列中所有项目总和的最佳算法

我遇到了问题，并提供了一个OK-ish解决方案。我希望有更好的解决方案。寻找任意子阵列中所有项目总和的最佳算法

问题

我有大约20万整数数组。给定两个指数i1和i2，我需要计算i1和i2之间所有元素的总和。数组中的每个整数都在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个元素长的段。对于上面的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])]

然后给出两个指数，现在有可能制定出subsection_sum在O（log n）的时间。例如，subsection_sum（a，2，7）== quarters [1] + halfves [1]。

来源

2011-05-22 Bernie Sumption

介绍一个包含累计和的辅助数组。也就是说，辅助阵列的元素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开始。辅助数组可以被视为缓存总和值为零，subsection_sum(a, 0, i)，全部为i。

来源

2011-05-22 14:26:02

完美，我不敢相信我想到了这样一个复杂的解决方案，错过了一个简单的解决方案！谢谢。 – 2011-05-22 14:36:39

与我的解决方案一样，但是却击败了我！ +1 – 2011-05-22 14:38:08

如果可以承受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

然后你就可以使用此表通过采取差别

lookupTable[i2] - lookupTable[i1]

这需要一定的时间来计算i1和i2之间array所有元素的总和。

来源

2011-05-22 14:33:52

我想说，我们提出了很好的补充说明。 – 2011-05-22 14:40:03

寻找任意子阵列中所有项目总和的最佳算法

回答

相关问题