一、题目
1、原题链接
3956. 截断数组
2、题目描述
给定一个长度为 n 的数组 a1,a2,…,an。
现在，要将该数组从中间截断，得到三个非空子数组。
要求，三个子数组内各元素之和都相等。
请问，共有多少种不同的截断方法？
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
输出一个整数，表示截断方法数量。
数据范围
前六个测试点满足 1≤n≤10。所有测试点满足 1≤n≤105，−10000≤ai≤10000。
输入样例1：
4
1 2 3 3
1
2
输出样例1：
1
1
输入样例2：
5
1 2 3 4 5
1
2
输出样例2：
0
1
输入样例3：
2
0 0
1
2
输出样例3：
0
1
二、解题报告
1、思路分析
思路来源：y总每日一题b站视频链接
y总yyds
（1）数据范围为105，需要将时间复杂度控制在 O(nlogn) 以内。
（2）首先判断所有元素总和是否能被3整除，如果不能被3整除，说明无法进行分割。如果可以被3整除，说明三个子数组的和均为sum/3。
（3）从前往后依次枚举第二个分割点，同时用num记录其前面有多少个位置的前缀和为sum/3。如果第二个分割点位置的前缀和为sum/3*2，则说明以该位置为第二分割点的分割方式总共有num种。直到遍历完所有第二分割点可能的位置，统计分割方式总数，输出即可。
2、时间复杂度
时间复杂度O(n)
3、代码详解
#include <iostream>
using namespace std;
const int N=100010;
typedef long long LL;
int n,a[N],s[N];
LL ans; //注意ans范围，最多从10^5-1个位置选两个分割点，所以总方案数超出int范围(10^9)，要设置成long long
int main(){
cin>>n;
int num=0;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i]; //计算前缀和
}
int sum=s[n];
//如果所有元素之和不是3的倍数，则无法分割成3个总和相等的子数组
if(sum%3!=0){
cout<<0;
}
else{
for(int i=2;i<n;i++){ //注意i从2到n-1,保证第一个子数组和最后一个子数组最少有一个数
if(s[i-1]==sum/3) num++; //记录从1位置到i位置一共有多少个位置的前缀和为sum/3
if(s[i]==sum/3*2) ans+=num; //如果当前位置满足前缀和=sum/3*2，说明以当前位置为第二个分割点，第一个分割点总共有num个，以该位置为第二分割点的总分割数即为num个
}
cout<<ans;
}
return 0;
}
三、知识风暴
一维前缀和
一维前缀和可以快速计算某一个指定区间内的元素和。
给定数组num[1],num[2],num[3],...,num[n]，设s[i]为前i个元素的前缀和,则有s[i]=s[i-1]+num[i](s[0]=0)。
若要求区间[a,b]（第a个数到第b个数的和，包含第a个数和第b个数），则为s[b]-s[a-1]。
