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

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分别

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])

因此,我们可以计算两个数组的元素之和并将它们相乘以获得系列的总和.

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)