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

淡淡的烟草味﹌ 2024-03-26 12:32 75阅读 0赞

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

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