3个不同数组的所有元素的总和

Question

我希望和优化的算法，以找到每个元素的数组和。

例如，let 3 array：

a = [1,2,3,4];
b = [5,6];
c = [8,9];

则最终总和将等于：

sum(1,5,8)+sum(1,5,9)+sum(1,6,8)+sum(1,6,9)+sum(2,5,8)...+sum(4,6,9)

我试过这样做，但我使用的算法的时间复杂度为O(n^3)，所以我想要任何低于这个复杂度的算法。

下面是我的算法：

sum = 0    
for(i=0;i<a.size();i++)
       for(j=0;j<b.size();j++)
          for(k=0;k<c.size();k++)
              sum = sum+a[i]+b[j]+c[k];

Answer 1

在本例中，a、b和c分别有4、2和2个元素。如果您想将它们添加到每种组合中，将会有4 * 2 * 2 = 16术语需要添加。在这些术语中，a的每个元素将出现4次，因为它将被添加到b和c元素的2 * 2 = 4组合中。类似地，b (或c)的每个元素将出现8次，因为它将被添加到a和c (或b)的每个元素的每个4 * 2 = 8组合中。

因此，在最终的和中，a的每个元素将出现4次，b和c的每个元素将出现8次。一旦你弄清楚了，你可以做更少的乘法和加法来得到结果。(只需对单个数组的元素求和，然后将这些和分别乘以4，8和8)。

Answer 2

a的每个元素将与b的每个元素和c的每个元素一起出现在一起。

这意味着a中的每个元素都将以与b.length * c.length相等的数量出现。

这也很容易从蛮力伪代码中看出：(为了可读性进行了修改)

for i = 0 to a.length
   for j = 0 to b.length     // happens once for each i
      for k = 0 to c.length  // happens b.length times for each i
         sum += a[i] + ...   // happens b.length * c.length times for each i

概括地说，我们提出了以下算法：

对所有元素求和，将结果与b.length * c.length.

• Sum

• a相乘，将结果与b.length * c.length.

• Sum all elements c相乘，将结果与上述三个值相加相乘。

这是一种O(n)算法，其中n是元素的总数或每个数组的平均元素数。