《蓝桥杯每日一题》 前缀和·Acwing 3956. 截断数组

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：

4
1 2 3 3

输出样例1：

1

输入样例2：

5
1 2 3 4 5

输出样例2：

0

输入样例3：

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);}
}

感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下