喜欢切数组的红

1. 使用BufferedReader, PrintWriter StringTokenizer 加快IO速度避免超时
2. 使用前缀和快速判断区间内元素和是否满足要求
3. 使用整数计数数组快速判断区间内是否包含正数
4. 如果总和不能被3整除, 直接返回0
5. 两层for循环查找有效分割点

• 第一层 for 找到第一个有效分割点
• 第二层for在第一个分割点后面找有效的第二个分割点
• 通过判断每个分割点后是否还有整数进行剪枝
• 每次找到一对分割点, 结果++

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = Integer.parseInt(in.nextLine());
            int sum = 0;
            int[] arr = new int[n];
            for(int i = 0; i < n; i++){
                arr[i] = in.nextInt();
                sum += arr[i];
            }
            if(sum % 3 != 0){
                System.out.println(0);
                continue;
            }
            int avg3 = sum / 3;
            int sum1 = 0;//第一个子数组和
            int count = 0;
            int rightIndex = n - 1;
            int firstflag = 0;//第一个数组是否有正数
            int secondflag = 0;//第三个数组是否有正数
            for(int i = 0; i < rightIndex - 3; i++){
                firstflag = Math.max(firstflag,arr[i]); 
                sum1 += arr[i];
                //从左往右找到第一刀
                if(sum1 == avg3 && firstflag > 0){
                    int sum2 = 0;//第三个子数组和
                    //从右往左找到第二刀
                    secondflag = 0;
                    for(int j = rightIndex; j >= i+2; j--){
                        secondflag = Math.max(secondflag,arr[j]);
                        sum2 += arr[j];
                        if(sum2 == avg3 & secondflag > 0 && hasZhengShu(arr,i + 1,j)){
                            count++;
                        }
                    }
                }
            }
            System.out.println(count);
        }
    }

    //判断数组内是否有正数
    static boolean hasZhengShu(int[] arr, int i, int j){
        for(; i < j; i++){
            if(arr[i] > 0){
                return true;
            }
        }
        return false;
    }
}