Python高效计算整数序列两两元素乘积之和：O(N)复杂度实现及要点解析

要计算整数序列中所有不同元素两两乘积的和，可以采用数学优化方法避免双重循环。以下是Python实现代码： ```python def sum_pairwise_products(A): total_sum = sum(A) sum_of_squares = sum(a*a for a in A) return (total_sum * total_sum - sum_of_squares) // 2 # 示例用法 A = [1, 2, 3] result = sum_pairwise_products(A) # 输出11 (1*2 + 1*3 + 2*3 = 2 + 3 + 6) ``` 代码逻辑说明： 1. 计算序列总和total_sum 2. 计算各元素平方和sum_of_squares 3. 利用公式 (total_sum² - sum_of_squares)/2 得到结果 数学原理： ∑(i<j)Ai×Aj = [ (∑Ai)² - ∑(Ai²) ] / 2 时间复杂度：O(N) 空间复杂度：O(1) 需要注意的逻辑点： 1. 当序列元素值较大时，total_sum的平方可能溢出，需考虑使用大整数类型 2. 对于空序列或单元素序列，结果应为0 3. 公式中的除法必须用整数除法//，因为平方差必定是偶数 ######[AI写代码神器 | 279点数解答 | 2025-06-02 18:47:29]