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

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

给定一个长度为 n的数组 a1,a2,…,an。

现在，要将该数组从中间截断，得到三个非空子数组。

要求，三个子数组内各元素之和都相等。

请问，共有多少种不同的截断方法？

输入格式

第一行包含整数 n。

第二行包含 n个整数 a1,a2,…,an。

输出格式 输出一个整数，表示截断方法数量。

数据范围 前六个测试点满足 1≤n≤10。

所有测试点满足 1≤n≤105，−10000≤ai≤10000。

输入样例1： 4 1 2 输出样例1： 1 输入样例2： 5 1 2 4 5 输出样例2： 0 输入样例： 2 0 0 输出样例： 0

算法思路

这是一个前缀和的应用，如果这个数组可以分割，那么代表这个数组的总和对三取余为0。

然后如何统计分割次数了，在可以分的前提下，如果当前的数的前缀和是总和的1/的时候，代表的是这个可以分割了，后面的那1/就是固定的了，那么结果就可以加上了，如果当前数的前缀和是总和的1/，那么代表这是一个新的方式，那么当前可以加的tmp就需要+1。

C++版本

#include<bits/stdc++.h>
using namespace std;

int n;
ct int  = 1e5 + 10;
int num[];
long long sum;


int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> num[i];
        sum += num[i];
    }
    if(sum %  != 0) cout << "0";
    else 
    {
        long long ave = sum / ;
        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  = 100010;
    static int n, m;
    static long res;
    static int[] a = new int[];
    static int[] s = new int[];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);

        n = ();
        for (int i = 1; i <= n; i ++) a[i] = ();
        for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];

        if (s[n] %  != 0 || n < )
        {
            println(0);
            return;
        }

        int dex = s[n] / ;
        for (int i = 1; i < n; i ++)
        {
            if (s[i] == dex * 2) res += m;
            if (s[i] == dex) ++ m;
        }

        println(res);
    }
}