另一个思路，首先就是如果要三份的和相等，那么数组的总和一定是三的倍数，并且第一份的总和是数组总和的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)

警示后人：十年OI一场空，不开long long见祖宗

题解

思考了一下,只要枚举前缀是否为总和的1/3即可

void solve() {
    int n;
    cin >> n;
    vl a(n + 1);
    vl s(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    if (n < 3 || s[n] % 3 != 0) {
        cout << 0 << "\n";
        return;
    }

    ll cnt1 = s[n] / 3;
    ll cnt2 = 2 * cnt1;
    ll ans = 0;
    ll cnt = 0;

    for (int i = 1; i < n; i++) {
        if (s[i] == cnt2) {
            ans += cnt;
        }
        if (s[i] == cnt1) {
            cnt++;
        }
    }
    cout << ans << "\n";
}

import os
import sys
n = int(input())
a = map(int, input().split())
s = [0]
for i in a:
    s.append(s[-1] + i)
t = s[-1] // 3
if t * 3 != s[-1]:
    print(0)
else:
    c0 = 0
    c1 = 0
    ind = []
    for i0 in range(1, len(s)):
        i = s[i0]
        if i == t:
            c0 += 1
            ind.append(i0)
        elif i == s[-1] - t:
            c1 += 1
    if t != 0:
        print(c0 * c1)
    else:
        r = 0
        for i in range(len(ind)):
            for j in range(i + 1, len(ind)):
                if ind[j] == n:
                    continue
                r += 1
            
        print(r)

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)

一个暴力的前缀和思路，可以拿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)