1.题目
https://www.acwing.com/problem/content/3959/
给定一个长度为 n 的数组a1,a2,…,an。
现在，要将该数组从中间截断，得到三个非空子数组。
要求，三个子数组内各元素之和都相等。
请问，共有多少种不同的截断方法？
输入格式
第一行包含整数 n。
第二行包含 n 个整数a1,a2,…,an。
输出格式
输出一个整数，表示截断方法数量。
数据范围
前六个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤10的五次方，−10000≤ai≤10000。
输入样例1：
1. 4 2. 1 2 3 3
输出样例1：
1
输入样例2：
1. 5 2. 1 2 3 4 5
输出样例2：
0
输入样例3：
1. 2 2. 0 0
输出样例3：
0
2.思路分析
既然要分配三个非空子数组，且值相同，那么不存在元素个数小于3，不存在原数组总和%3!=0的情况
pres[]为前缀和数组，perSum=原数组总和/3
那么我们只需要找到一个位置 pres[i]==perSum*2
此时res+=（pres[1~i-1]==averge)即可
因为第i位 满足2*perSum，pres[i+1~n]==perSum
所以只需要加上能使前i位的数组 分为 两个值为averge的位置 的数量即可
3.Ac代码
import java.io.*; public class Main { static int N=100010; public static void main(String[] args) throws IOException { int n; BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); n=Integer.parseInt(br.readLine()); String []s=br.readLine().split(" "); int []arr=new int[N]; //初始化初始数组 for (int i = 1; i <=n; i++) arr[i]=Integer.parseInt(s[i-1]); int []pres=new int[N]; //求前缀和数组 for (int i = 1; i <=n; i++) pres[i]=pres[i-1]+arr[i]; //如果个数小于3，或者前缀和不是3的倍数，那么无法截断 if(n<3 ||pres[n]%3!=0){ System.out.println("0"); return; } long perSum=pres[n]/3,res=0,fir = 0,t=0; //要给最后一个元素留下了，给第三个截断用 for (int i = 1; i <n; i++) { t=pres[i]; if(t==perSum*2) res+=fir; if(t==perSum) fir++; //不能调换这两个if判断的原因是，如果当前t等于perSum和perSum*2时（比如0特判等），就会出现在同一位自加 //一旦出现自加，那么可以理解为中间那个截断元素个数为0，这是不可能的 } System.out.println(res); } }
