喜欢切数组的红

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int nums = in.nextInt();
        int array[] = new int[nums];
        int sum = 0;
        for (int i = 0; i < nums; i++) {
            array[i] = in.nextInt();
            sum = sum + array[i];
        }
        int target = sum / 3;
        int sumOfPart = 0;
        ArrayList<Integer> indexLeftList = new ArrayList<>();
        ArrayList<Integer> indexRightList = new ArrayList<>();
        boolean positive = false;;
        for (int i = 0; i < array.length; i++) {
            if (array[i] > 0) {
                positive = true;
            }
            sumOfPart += array[i];
            if (sumOfPart == target && positive) {
                indexLeftList.add(i);
            }
        }
        sumOfPart = 0;
        positive = false;
        for (int i = array.length - 1; i >= 0; i--) {
            if (array[i] > 0) {
                positive = true;
            }
            sumOfPart += array[i];
            if (sumOfPart == target && positive) {
                indexRightList.add(i);
            }
        }
        int count = 0;
        for(int i = 0;i<indexLeftList.size();i++){
            for(int j = j=0;j<indexRightList.size();j++){
                if(indexLeftList.get(i)<indexRightList.get(j)){
                    if(isValid(indexLeftList.get(i),indexRightList.get(j),array,target)){
                        count++;
                    }
                }
            }
        }
        System.out.print(count);
    }
    public static boolean isValid(int left,int right,int[]nums,int target){
        int sum = 0;
        boolean positive = false;
        for(int i = left+1;i<=right-1;i++){
            if (nums[i] > 0) {
                positive = true;
            }
            sum+=nums[i];
        }
        if(sum==target && positive){
            return true;
        }else{
            return false;
        }
    }

}

10
0 3 4 2 3 2 1 -1 3 4

while 1:
    try:
        n = int(input())
        ls = list(map(int,input().split()))
        if sum(ls)%3 != 0:
            print(0)
            break
        ans1 = sum(ls)//3
        ans2 = ans1*2
        sumls = [0]
        pls = [0]
        for i in range(n):
            sumls.append(sumls[-1]+ls[i])
            if ls[i]>0:
                pls.append(pls[-1]+1)
            else:
                pls.append(pls[-1])
        sumls = sumls[1:]
        pls = pls[1:]
        count = 0
        ans1ind = []
        ans2ind = []
        for i in range(n):
            if sumls[i]==ans1 and pls[i]>0:
                ans1ind.append(i)
            elif sumls[i]==ans2 and pls[-1]-pls[i]>0:
                ans2ind.append(i)
        for x in ans1ind:
            for y in ans2ind:
                if x<y and pls[y]-pls[x]>0:
                        count += 1
        print(count)
        break
    
    except:
        break

#include <stdio.h>

int main() {
    int n = 0;
    scanf("%d", &n);
    int a[200000] = {0};
    int sum = 0;
    int s[200000] = {0};//前缀和
    int d1[200000] = {0};//1/3位置
    int d2[200000] = {0};//2/3位置
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        sum += a[i];
        s[i] = sum;
    }
    int result  = 0;
    if (sum != 0) {
        if (sum % 3 == 0) {
            int cnt1 = 0;
            int cnt2 = 0;

            for (int i = 0; i < n ; i++) {
                if (s[i] == sum / 3) {
                    int flag = 0;//前1/3有正数
                    for (int j = 0; j <= i; j++) {
                        if (a[j] > 0) {
                            flag = 1;
                            break;
                        }
                    }
                    if (flag) {
                        d1[cnt1++] = i;
                        flag = 0;
                    }

                }
            }
            for (int i = n - 1; i >= 0 ; i--) {
                if (s[i] == 2 * sum / 3) {
                    int flag = 0;//后1/3有正数
                    for (int j = n - 1; j >= i; j--) {
                        if (a[j] > 0) {
                            flag = 1;
                            break;
                        }
                    }
                    if (flag) {
                        d2[cnt2++] = i;
                        flag = 0;
                    }
                }
            }

            //结果
            for (int i = 0; i < cnt1; i++) {
                for (int j = 0; j < cnt2; j++) {
                    if (d2[j] > d1[i]) {
                        //中间1/3有正数
                        int flag = 0;
                        for (int k = d1[i]; k <= d2[j]; k++) {
                            if (a[k] > 0) {
                                flag = 1;
                                break;
                            }
                        }
                        if (flag) {
                            result++;
                            flag = 0;
                        }
                    }
                }
            }
        }
    } 
    // else if (sum == 0) {
    //     int cnt = 0;
    //     for (int i = 0; i < n ; i++) {
    //         if (s[i] == 0) cnt++;
    //     }
    //     cnt--;
    //     result = cnt * (cnt - 1) / 2;
    // }
    printf("%d", result);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long sum = 0;

    vector<long long> nums(n);
    vector<long long> presum(n+1);//前i个数字的前缀和
    vector<int> dp(n+1);//前i个数字有几个正数
    for (int i = 0; i<n; ++i)
    {
        cin >> nums[i];
        sum += nums[i];
    }
    
    //加工前缀和数组，正数统计数组
    
    for (int i = 1; i<=n; ++i)
    {
        presum[i] = presum[i-1]+nums[i-1];

        //真几把无语，这还非得加个括号，我找半天错误，原来是这
        dp[i] = dp[i-1] + (nums[i-1] > 0 ? 1 : 0);   
    }
    if (sum%3 != 0 || dp[n] == 0)
    {
        cout << 0;
        return 0;
    }

    long long target = sum/3;
    int ans = 0;
    for (int i = 1; i<=n; ++i)
    {
        //前i个数字累加和为1/3的sum，且有正数
        if (presum[i] == target && dp[i] > 0)
        {
            
            for (int j = i+1; j<=n; ++j)
            {
                //前j个数字累加和为2/3的sum，且每段都有正数
                if (presum[j] == 2*target && dp[j] - dp[i] > 0 && dp[n] - dp[j] > 0)
                {
                    ans++;
                }
            }
        }
    }
    cout << ans;
}
// 64 位输出请用 printf("%lld")

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> presum(n + 1, 0);
    vector<int> poscount(n + 1, 0);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        presum[i + 1] = presum[i] + a;
        poscount[i + 1] = poscount[i] + (a > 0 ? 1 : 0);
    }
    int sumtotal = presum[n];
    if (sumtotal % 3 != 0 ) {
        cout << 0 << endl;
        return 0;
    }
    int sum = sumtotal / 3;
    int count = 0, result = 0;
    for (int i = 1; i <= n - 2; i++) {
        int suma = presum[i];
        if (sum != suma || poscount[i] <= 0)
            continue;
        for (int j = i + 1; j <= n - 1; j++) {
            int sumb = presum[j] - presum[i];
            int numb = poscount[j] - poscount[i];
            if (sum != sumb || numb <= 0)
                continue;

            int sumc = sumtotal - presum[j];
            int numc = poscount[n] - poscount[j];
            if (sumc == sum && numc > 0)
                result++;
        }

    }
    cout << result << endl;
    return 0;
}

我用的时间复杂度较高，但是这题能过；大致思路是先找到一个和能为sum/3的值，
再去搜索以这个节点为第一刀能砍第二刀的位置，然后回溯，找到下一个第一刀能在的位置
以此为基点去找第二刀，直到遍历完所有可能的第一刀
import java.util.Scanner;

import java.util.ArrayList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int sums=0;
        int a[]=new int[n];
        for(int i=0;i<n;++i){
            a[i]=in.nextInt();
            sums+=a[i];
        }
        if(sums%3!=0){
            System.out.println(0);
        }else{
            int tempsum=sums/3;
        jrun(a,new ArrayList<Integer>(),0,tempsum);
        System.out.println(Acount);
        }
    }
    static int Acount=0;
    private static void jrun(int []an,ArrayList<Integer> path,int begin,int sum){
        int sumnow=0;
        if(path.size()==2){
            Acount++;
            return;
        }
        boolean flag=false;
        for(int i=begin;i<an.length;++i){  
            if(an[i]>0){flag=true;}
            sumnow+=an[i];
            if(sumnow==sum&&flag){
                ArrayList<Integer> path1=new ArrayList<Integer>(path);
                path1.add(i);
                jrun(an,path1,i+1,sum);
            }
        }


    }
}

def solve():
    n = int(input().strip())
    items = [int(i) for i in input().strip().split(" ")]
    isum = sum(items)
    if isum % 3 != 0:
        print(0)
        return
    isum3 = isum // 3

    # 找到两侧第一个正数下标
    # 实际测试时不管l,r也过了，就很怪
    l = 0
    while l < n:
        if items[l] > 0:
            break
        l += 1

    r = n - 1
    while r >= 0:
        if items[r] > 0:
            break
        r -= 1

    prefix_sum = [0] * (n + 1)
    n_13 = 0  # 当前左侧前缀和与isum3可用交点数量
    n_13_candidate = 0 # 还不可用的交点数量，得遇到一个正数才能加到上面去
    n_cuts = 0
    for i in range(r):
        prefix_sum[i] = prefix_sum[i - 1] + items[i]  # 0 - 1 = -1，对Python来说这个下标无妨
        if items[i] > 0:
            n_13 += n_13_candidate
            n_13_candidate = 0
        if prefix_sum[i] == isum3 and i >= l:
            n_13_candidate += 1
        if prefix_sum[i] == 2 * isum3:
            n_cuts += n_13
    print(n_cuts)


solve()

k = int(input())
nums = list(map(int, input().split()))


def count_solution(nums_list):
    sum_list = []
    positive_list = []
    sum_temp = 0
    for num in nums_list:
        if num > 0:
            positive_list.append(1)
        else:
            positive_list.append(0)
        sum_temp += num
        sum_list.append(sum_temp)
    first_son_sum = sum_list[-1] / 3
    # 寻找第一次分割
    frist_maybe_c = sum_list.count(first_son_sum)
    if frist_maybe_c == 0:
        return 0
    else:
        frist_maybe_index = []
        i = -1
        while len(frist_maybe_index) < frist_maybe_c:
            i = sum_list.index(first_son_sum, i + 1)
            frist_maybe_index.append(i)
        # 寻找第二次分割位置
        second_maybe_index = []
        second_son_sum = 2 * first_son_sum
        second_maybe_c = sum_list.count(second_son_sum)
        i = 0  # 第二次不可能从第一位开始分割
        while len(second_maybe_index) < second_maybe_c:
            i = sum_list.index(second_son_sum, i + 1)
            # 防止出现和为零时导致第二次分割的位置在末尾
            if i < len(nums_list):
                second_maybe_index.append(i)
        all_solotion = []
        for m in frist_maybe_index:
            for n in second_maybe_index:
                if m < n:  # 呃附着的出现可能会导致N大于M
                    # 保证三个数组都有正shu存在
                    if (
                        sum(positive_list[: m + 1]) > 0
                        and sum(positive_list[m : n + 1]) > 0
                        and sum(positive_list[n:]) > 0
                    ):
                        all_solotion.append([m, n])
    return len(all_solotion)


print(count_solution(nums))
#超时，通过率50%，就当给大家提供思路吧