如何高效计算两个数组所有元素对的乘积和（优化O(n²)复杂度）

而且思路非常巧妙——利用数学公式就能把时间复杂度从O(n²)（准确说是O(mn)，当两个数组长度分别为m和n时）直接降到O(m+n)，甚至在已知元素范围的情况下能做到O(1)！

核心原理：乘法分配律的妙用 #

所有元素对的乘积之和，本质上就是两个数组元素和的乘积。展开这个乘积你就能明白：

(a₁ + a₂ + ... + aₘ) × (b₁ + b₂ + ... + bₙ) = a₁b₁ + a₁b₂ + ... + a₁bₙ + a₂b₁ + ... + aₘbₙ

这完全就是题目要求计算的总和！

用题目示例验证 #

拿你给出的例子：

• A=[1,2,3,4]的元素和是 1+2+3+4=10
• B=[1,2,3]的元素和是 1+2+3=6
• 两者乘积为 10×6=60，和手动计算所有元素对乘积的总和完全一致。

复杂度对比 #

• 暴力法：需要遍历所有m×n个元素对，时间复杂度O(mn)，当数组规模较大时（比如m、n都是10^5），性能会急剧下降；
• 求和相乘方法：只需要分别遍历两个数组各一次求和，时间复杂度O(m+n)，效率提升非常明显；
• 已知元素范围的优化：题目提到两个数组的元素范围是1..m和1..n，我们可以直接用等差数列求和公式，连数组都不用遍历：
  sum_A = m*(m+1)//2
  sum_B = n*(n+1)//2
  这样时间复杂度直接降到O(1)。

代码示例 #

用Python实现两种场景：

# 给定具体数组的情况
def product_sum_from_arrays(A, B):
    return sum(A) * sum(B)

# 已知元素范围是1..m和1..n的情况
def product_sum_from_range(m, n):
    sum_A = m * (m + 1) // 2
    sum_B = n * (n + 1) // 2
    return sum_A * sum_B

测试结果：

• product_sum_from_arrays([1,2,3,4], [1,2,3]) → 返回60
• product_sum_from_range(4, 3) → 返回60

总结 #

这个方法的核心是利用数学上的乘法分配律，把双重循环的问题转化为两个单次求和的问题，大幅降低了时间复杂度，尤其适合处理大规模数组的场景。

内容的提问来源于stack exchange，提问作者pranay