题目描述
现在,要将该数组从中间截断,得到三个非空子数组。
要求,三个子数组内各元素之和都相等。
分析
要将整个数组分为三段,需要切两刀,将每一份数组分为s/3
。
如果依次枚举两个位置,时间复杂度是O(n*n)
级,会tle
。
注:由于是在10的5次方中选2个点,ans的个数是(10^5)的平方再除2,为5*10的9次方级,所以会暴int,需要开long来存储ans。
所以,我们只能枚举1
个位置,将时间复杂度控制在O(n*logn)
级。
习惯上,我们枚举第2
个位置,将第2
个位置分为n-2
种情况,再把每种情况的方案数加起来即可。
怎么确定方案数?
假设我们固定了第2
个位置,即在2s/3
的位置,也就是确定了第2
刀。
那么方案数就取决于前面的第1刀的个数
那么第1刀切在哪?
第1刀需要切在s/3的位置,用cnt
统计有多少个s/3
,再到2s/3
的位置时将cnt
加上即可。
分析图
AC code
import java.io.*;
public class Main{
static int N=100010,n;
static int []s= new int[N];
static long ans;
public static void main(String []args) throws IOException {
//快读快写,n*a=10^5*10^4=10的9次方
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
n=Integer.parseInt(in.readLine());
String []s1=in.readLine().split(" ");
for(int i=1;i<=n;i++)s[i]=s[i-1]+Integer.parseInt(s1[i-1]);
//求得每个点的前缀和
//题目要求三个子数组内各元素之和都相等。
//也就是s[n]可以平均分为3等份,就让s[n]%3不余0表示不能均分3等份
if(s[n]%3!=0)out.println(0);
else {
long avg=s[n]/3,cnt=0;//cnt计数
for(int i=1;i<n;i++) {
if(s[i]==avg*2)ans+=cnt;
//找到一个前缀和等于2倍的avg,在这截断,截断选择看cnt的个数。
//剩下的1/3部分已是默认截断处理
if(s[i]==avg)cnt++;
//找到一个前缀和等于avg,就加1,表示可以从这截断。
}
out.println(ans);
}
out.flush();
}
}