n = int(input()) a = list(map(int, input().split()))

pre_sum = [0] * (n + 1) for i in range(1, n + 1): pre_sum[i] = pre_sum[i - 1] + a[i - 1]

total = pre_sum[n] if total % 3 != 0: print(0) else: target = total // 3 res = 0 count = 0

for j in range(1, n): 
    if pre_sum[j] == 2 * target:
        res += count
    if pre_sum[j] == target:
        count += 1

print(res)

另一个思路，首先就是如果要三份的和相等，那么数组的总和一定是三的倍数，并且第一份的总和是数组总和的1/3，前两份的是2/3，也就是说，我们不需要分开枚举两个间隔点i和j，实际上可以同时枚举，i这点的前缀和很好理解就是1/3总和，我们找看看有多少个i可以切前1/3，计其个数为cnt，然后再找j，也就是切前2/3的，如果遇到了可行的j，那么总方案数会+=cnt，因为这个j可以和前面所有可行的i构成cnt种方案，以此类推找到所有可行的i和j并且算好总方案数ans，复杂度为O(n)

import sys
input = lambda:sys.stdin.readline().strip()

n=int(input())
a=[0]+list(map(int,input().split()))
s=[0]*len(a)

for i in range(1,n+1):
    s[i]=s[i-1]+a[i]

if s[n] % 3 != 0:
    print(0)
    exit(0)

tar = s[n] // 3
ans = 0
cnt = 0

for j in range(2, n):
    if s[j-1] == tar:
        cnt += 1
    if s[j] == 2 * tar:
        ans += cnt
print(ans)

一个暴力的前缀和思路，可以拿70%，复杂度O(n**2)

import sys
input = lambda:sys.stdin.readline().strip()

n=int(input())
a=[0]+list(map(int,input().split()))
s=[0]*len(a)

for i in range(1,n+1):
    s[i]=s[i-1]+a[i]

ans=0
for i in range(2,n): # i 2~n-1
    for j in range(i,n): # j i~n-1
        if s[i-1]-s[0]==s[j]-s[i-1]==s[n]-s[j]:ans+=1

print(ans)