截断数组（蓝桥杯每日一题）-蒲公英云

截断数组（蓝桥杯每日一题）

给定一个长度为 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);
    }
}