截断数组（蓝桥杯每日一题）
给定一个长度为 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：
1
输入样例2：
5
1 2 3 4 5
输出样例2：
0
输入样例3：
2
0 0
输出样例3：
0
算法思路
这是一个前缀和的应用，如果这个数组可以分割，那么代表这个数组的总和对三取余为0。
然后如何统计分割次数了，在可以分的前提下，如果当前的数的前缀和是总和的1/3的时候，代表的是这个可以分割了，后面的那1/3就是固定的了，那么结果就可以加上了，如果当前数的前缀和是总和的1/3，那么代表这是一个新的方式，那么当前可以加的tmp就需要+1。
C++版本
#include<bits/stdc++.h> using namespace std; int n; const int N = 1e5 + 10; int num[N]; long long sum; int main() { cin >> n; for (int i = 1; i <= n; ++ i) { cin >> num[i]; sum += num[i]; } if(sum % 3 != 0) cout << "0"; else { long long ave = sum / 3; long long nowSum = 0, tmp = 0; long long ans = 0; for (int i = 1; i < n; ++ i) { nowSum += num[i]; if (nowSum == 2 * ave) ans += tmp; if (nowSum == ave) ++ tmp; } cout << ans << endl; } return 0; }
Java版本
import java.util.*; public class Main{ static int N = 100010; static int n, m; static long res; static int[] a = new int[N]; static int[] s = new int[N]; public static void main(String[] args){ Scanner scan = new Scanner(System.in); n = scan.nextInt(); for (int i = 1; i <= n; i ++) a[i] = scan.nextInt(); for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i]; if (s[n] % 3 != 0 || n < 3) { System.out.println(0); return; } int dex = s[n] / 3; for (int i = 1; i < n; i ++) { if (s[i] == dex * 2) res += m; if (s[i] == dex) ++ m; } System.out.println(res); } }
