j:第三个数组的第一个元素
i:第二个数组的最后一个元素
由于O(nlog)的复杂度上限,我们只能最多枚举一个点(固定一个点)
另一个点可以通过预处理解决:
cnt[i]:记录[1,i]中区间和为sum/3的次数
由于前缀和的性质,我们枚举第二个点(枚举第一个点会导致冲突)
Python 代码
n = int(input())
x = 0
s = [0] + list(map(int, input().split()))
for i in range(1, n + 1):
s[i] += s[i - 1]
if s[n] % 3 != 0:
print(0)
else:
x = s[n] // 3
cnt = [0] * (n + 1)
for i in range(1, n + 1):
cnt[i] += cnt[i - 1]
if s[i] == x: cnt[i] += 1
res = 0
for i in range(2, n - 1 + 1): # 由于分割后的数组不能为空,i属于第二个数组因此取值范围为:[2,n-1]
if s[i] == x * 2:
res += cnt[i - 1] # 由于i点属于第二个数组,因此不能取到
print(res)