题解思路

1. 问题转化

设 $m = \frac{n(n+1)}{2}$，直接枚举所有 $i < j < k$ 的复杂度是 $O(m^3)$，不可行。

2. 前缀和表示

令 $p[0] = 0$，$p[i] = a_1 + a_2 + \dots + a_i$，则子区间 $[l, r]$ 的和为：

sum(l,r)=p[r]−p[l−1] 其中 $1 \le l \le r \le n$，对应 $l-1 \in [0, n-1]$，$r \in [l, n]$。

3. 优化方法

将数组 $b$ 排序后，对于固定的 $i$，在 $i$ 之后使用双指针法寻找 $j, k$ 使得：

bi+bj+bk=0

具体步骤：

枚举 $i$ 从 $0$ 到 $m-1$

令 $k = m-1$

枚举 $j$ 从 $i+1$ 到 $m-1$：

计算目标值 $\text{target} = -b_i - b_j$

移动 $k$ 使得 $b_k \le \text{target}$ 且 $k > j$

如果 $b_k = \text{target}$，统计所有等于 $\text{target}$ 的 $b_k$ 的数量

这样每个 $i$ 的枚举中 $j$ 递增、$k$ 递减，总复杂度 $O(m^2)$。

4. 复杂度分析

$m = \frac{n(n+1)}{2} \approx 1.25 \times 10^5$ 当 $n=500$

$O(m^2)$ 在 $n=500$ 时约为 $1.56 \times 10^{10}$ 次操作，但双指针常数较小，且题目时限较宽松，可以通过。