乘积求和问题的优化解法：从TLE到高效计算

我们可以对原问题的计算方式进行优化，避免使用双重循环，从而降低时间复杂度。 原问题要求计算 $S = a_1\cdot a_2 + a_1\cdot a_3+\cdots + a_1\cdot a_n + a_2\cdot a_3+\cdots + a_{n - 2}\cdot a_{n - 1}+a_{n - 2}\cdot a_n + a_{n - 1}\cdot a_n$。 我们知道 $(a_1 + a_2+\cdots + a_n)^2=a_1^2 + a_2^2+\cdots + a_n^2+2(a_1\cdot a_2 + a_1\cdot a_3+\cdots + a_1\cdot a_n + a_2\cdot a_3+\cdots + a_{n - 2}\cdot a_{n - 1}+a_{n - 2}\cdot a_n + a_{n - 1}\cdot a_n)$。 那么 $S=\frac{(\sum_{i = 1}^{n}a_i)^2-\sum_{i = 1}^{n}a_i^2}{2}$。 以下是优化后的Python代码： ```python n = int(input()) # 读取输入的n个整数 nums = list(map(int, input().split())) # 计算所有数的和 total_sum = sum(nums) # 计算所有数的平方和 square_sum = sum([i ** 2 for i in nums]) # 按照公式计算结果 result = (total_sum ** 2 - square_sum) // 2 print(result) ``` ### 代码解释 1. **输入处理**：首先读取整数`n`，接着读取`n`个整数并存储在列表`nums`中。 2. **计算总和与平方和**：使用`sum`函数分别计算所有数的和`total_sum`以及所有数的平方和`square_sum`。 3. **计算最终结果**：根据推导的公式 $S=\frac{(\sum_{i = 1}^{n}a_i)^2-\sum_{i = 1}^{n}a_i^2}{2}$ 计算最终结果。 4. **输出结果**：将计算得到的结果输出。 ### 复杂度分析 - **时间复杂度**：$O(n)$，因为只需要对数组进行一次遍历。 - **空间复杂度**：$O(n)$，主要用于存储输入的整数列表。 ######[AI问答 | 566点数解答 | 2026-05-10 16:02:05]