考虑到 $(x + y) = x^2 + 2xy + y^2$

所以

$$\sum_{1 \leq i < j \leq n} (a_i + a_j)^2 = \sum_{1 \leq i < j \leq n} (a_i^2 + a_j^2 + 2a_ia_j) $$

我们令 $s1[i] = \sum_{j = 1}^ia_i$

$s2[i] = \sum_{j = 1}^ia_i^2$

所以原来的式子

$$\sum_{1 \leq i < j \leq n} (a_i + a_j)^2$$ $$= \sum_{1 \leq i < j \leq n} (a_i^2 + a_j^2 + 2a_ia_j) $$$$= \sum_{i = 1}^n(s2[i - 1] + (i - 1) \times a_i^2 + 2\times a_i \times s1[i - 1]) $$

故最后时间复杂度$O(n)$