从‘两两相乘求和’到‘平方和公式’，一个被忽略的数学技巧如何帮你秒杀算法题？
从‘两两相乘求和’到‘平方和公式’：数学技巧如何优化算法效率
在解决蓝桥杯LQ0014这类算法问题时，许多开发者会本能地采用暴力解法——直接计算所有两两组合的乘积之和。这种方法虽然直观，但当数据规模达到20万时，其O(n²)的时间复杂度将导致严重的性能瓶颈。实际上，这个问题背后隐藏着一个经典的数学恒等式，能将时间复杂度优化至O(n)。
1. 平方和公式的数学本质
两两相乘求和问题可以抽象为：给定n个数a₁, a₂, ..., aₙ，求所有不同元素对乘积之和S = Σaᵢaⱼ (i < j)。这个看似复杂的求和问题，其实可以通过简单的代数恒等式转化为更易计算的形式。
考虑所有元素和的平方展开：
(a₁ + a₂ + ... + aₙ)² = a₁² + a₂² + ... + aₙ² + 2(a₁a₂ + a₁a₃ + ... + aₙ₋₁aₙ)观察等式右边，可以发现它正好包含了我们需要的两两乘积项（系数为2）以及各元素的平方和。因此，我们可以通过重组这个等式得到：
S = [(Σaᵢ)² - Σaᵢ²] / 2这个转换的几何意义同样直观：想象一个边长为(a+b+c)的正方形，其面积可以分解为多个小正方形和长方形的组合。这种视觉化理解帮助我们记忆公式的本质而非死记硬背。
2. 算法实现的关键步骤
基于上述数学原理，我们可以设计出高效的算法实现。以下是使用C语言的两种优化方案对比：
2.1 前缀和法
#include <stdio.h> int main() { int n, a; long long sum = 0, psum = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a); sum += psum * a; psum += a; } printf("%lld\n", sum); return 0; }原理：动态维护前缀和psum，每个新元素都与之前所有元素和相乘后累加。时间复杂度O(n)，空间复杂度O(1)。
2.2 平方和公式法
#include <stdio.h> int main() { int n, a; long long sum = 0, sum1 = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a); sum += a; sum1 += a * a; } printf("%lld\n", (sum * sum - sum1) / 2); return 0; }优势：仅需单次遍历，同时计算元素和与平方和，最后套用公式。代码更简洁，数学意义更明确。
注意：当n较大时，sum²可能超出long long范围。在实际应用中需要考虑使用大整数类型或取模运算。
3. 性能对比与边界处理
三种方法的性能差异显著：
| 方法 | 时间复杂度 | 空间复杂度 | 适用数据规模 |
|---|---|---|---|
| 暴力枚举 | O(n²) | O(n) | n < 10⁴ |
| 前缀和 | O(n) | O(1) | n ≤ 10⁶ |
| 平方和公式 | O(n) | O(1) | n ≤ 10⁷ |
实际测试数据：
- 当n=2×10⁵时：
- 暴力法：超时（>1s）
- 前缀和：约0.12s
- 公式法：约0.08s
边界情况处理建议：
- 空输入或单元素输入（根据题意通常n≥2）
- 元素值全为0时的输出验证
- 极端大数测试（如所有aᵢ=1000，n=2×10⁵）
4. 数学思维的扩展应用
这个技巧的价值不仅在于解决特定编程题，更在于其广泛的应用场景：
统计学中的方差计算：
方差 = (Σxᵢ²)/n - (Σxᵢ)²/n²与我们的公式有异曲同工之妙
机器学习特征交互：当需要计算特征间的两两交互项时，类似方法可以避免显式计算所有组合
物理系统中的能量计算：在多体问题中，相互作用能常表示为粒子对之间的势能之和
金融组合风险分析：资产组合的风险计算涉及各资产收益率的两两协方差
进阶思考：如何将该方法推广到三元组乘积求和（如Σaᵢaⱼaₖ）？这需要更深入的多项式展开技巧：
(a+b+c+...)³ = a³+b³+c³+...+3(a²b+a²c+...)+6(abc+abd+...)掌握这种数学思维转换的能力，将使开发者能发现更多算法优化机会，而不仅仅是机械地编写代码。在解决实际问题时，先分析问题的数学本质，往往能找到比直接编码更高效的解决方案。