截断数组

朴素前缀和做法（超时）

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int a[N],n;
int main(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i],a[i]+=a[i-1];
    if(a[n]%3!=0) cout<<0;
    LL cnt = 0;
    for(int i=1; i<n; i++){
        for(int j=i+2; j<=n; j++){
            //[1,i] [j-1,i+1] [j,n]
            if(a[i] == a[j-1]-a[i] && a[j-1]-a[i] == a[n]-a[j-1])
                cnt++;
        }
    }
    cout<<cnt;
}

优化做法

因为要把数组均分三份，总和一定得是3的倍数，遍历前缀和数组，边扫描边记录哪些地方可以切第一刀，哪些地方可以切第二刀。如果位置j可以切第二刀，那么它与前面第一刀进行组合，就可以切成三部分。

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int a[N],n;
int main(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i],a[i]+=a[i-1];
    if(a[n]%3!=0){
        cout<<0;
        return 0;
    }
    int t = a[n]/3;
    LL ans = 0;
    for(int i=1, cnt=0; i<n-1; i++){
        if(a[i] == t) cnt ++;//i位置前面有多少可以切第一刀的地方
        if(a[n]-a[i+1] == t) ans += cnt;//第二刀切的位置
    }
    cout<<ans;
}