优化代码：解决原代码超时问题，将复杂度从 $O(n^2)$ 降至 $O(n)$

这段代码的时间复杂度是 $O(n^2)$，当 $n$ 较大时，会导致超时（TLE）。可以通过数学推导将时间复杂度优化到 $O(n)$。 推导过程如下： 假设数组元素为 $a_1, a_2, \cdots, a_n$，要求的和 $S=\sum_{1\leq i < j\leq n}a_i\times a_j$。 已知 $(a_1 + a_2+\cdots+a_n)^2=\sum_{i = 1}^{n}a_i^2+2\sum_{1\leq i < j\leq n}a_i\times a_j$。 则 $\sum_{1\leq i < j\leq n}a_i\times a_j=\frac{(\sum_{i = 1}^{n}a_i)^2-\sum_{i = 1}^{n}a_i^2}{2}$。 以下是优化后的代码： ```cpp #include <iostream> using namespace std; int main() { int n; // 读取整数 n cin >> n; int a[200005]; long long sum = 0; // 存储数组元素的和 long long squareSum = 0; // 存储数组元素平方的和 // 读取 n 个整数并计算元素和与元素平方和 for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; squareSum += (long long)a[i] * a[i]; } // 根据公式计算结果 long long S = (sum * sum - squareSum) / 2; // 输出结果 cout << S << endl; return 0; } ``` ######[AI问答 | 433点数解答 | 2026-05-10 16:04:01]