两个数组中所有元素对的乘积之和

Question

如果我们有两个数组，比如A=[1,2,3,4] 和 B=[1,2,3]，我们需要找到它们所有可能的数对乘积之和，即 1*1+1*2+1*3+2*1+2*2+2*3+3*1+3*2+3*3+4*1+4*2+4*3。当然我们可以用 O(n^2) 的时间复杂度解决这个问题，但是是否有更高效的方法呢？ 感谢您的帮助。 另外，两个数组中的整数范围分别为 1..m 和 1..n。

- pranay

---

你的意思可能是O(n*m)。 - Giorgi Moniava

Answer 1

这可以通过运用乘法分配律在加法上的运用，以 O(n+m) 时间完成。

所需的总和可以概括如下：

(A[0]*B[0] + A[1]*B[0] + ... + A[m-1]*B[0]) + (A[0]*B[1] + A[1]*B[1] + ... + A[m-1]*B[1]) + ... + (A[0]*B[n-1] + A[1]*B[n-1] + ... + A[m-1]*B[n-1])

注意，在每个部分求和中，我们可以因式分解出元素B。这一级数化简为：

(A[0] + A[1] + ... + A[m-1]) * B[0] + (A[0] + A[1] + ... + A[m-1]) * B[1] + ... + (A[0] + A[1] + ... + A[m-1]) * B[n-1]

注意，数组 A 中 所有 元素之和是上述序列中每个项的因子，可以将其分解出来得到：

(A[0] + A[1] + ... + A[m-1]) * (B[0] + B[1] + ... + B[n-1])

我们可以计算两个数组中元素的总和，并将它们相乘，以得到该系列的总和。

- EvilTak

Answer 2

1*1+1*2+1*3+2*1+2*2+2*3+3*1+3*2+3*3+4*1+4*2+4*3
=60

(1+2+3) * (1+2+3+4)
=60

为什么？

sum(B) + 2*sum(B) + 3*sum(B) + 4*sum(B)
sum(B) * sum(A)

- גלעד ברקן

Answer 3

我们可以观察到以下事实：

A = [1,2,3,4];
B = [1,2,3];
A * B = 
A[0] * B[0] + A[0] * B[1] + A[0] * B[2]+ .. +
A[3] * B[0] + A[3] * B[1] + A[3] * B[2] =
A[0] * (B[0]+B[1]+B[2]) + .. +
A[3] * (B[0]+B[1]+B[2]) = (A[0] + A[1] + A[2] + A[3]) * (B[0] + B[1] + B[2]) 

- Giorgi Moniava

Answer 4

正如其他人所说，您可以将公式重写为向量总和的乘积。

我不确定您的数组是否包含范围在1...n之间的任意值或确切范围。 如果它们包含范围在1...n之间的所有元素，则可以将1...n的总和重写为n*(n+1) / 2

- wolff