题解 | 喜欢切数组的红

预处理操作，提前准备一下两个数组一个是每个位置右侧第一个正数位置另一个是后缀合法数量，最后前缀处理累加一下就行

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        if (!in.hasNextInt()) return;
        
        int n = in.nextInt();
        long[] reds = new long[n]; // 元素可能很大，用 long 防止溢出
        long totalSum = 0;
        
        for (int i = 0; i < n; i++) {
            reds[i] = in.nextLong();
            totalSum += reds[i];
        }

        // 1. 不能被3整除，绝对无法平分
        if (totalSum % 3 != 0) {
            System.out.println(0);
            return;
        }

        long target = totalSum / 3;

        // 2. 预处理 nextPos 数组：nextPos[i] 表示从索引 i 开始，右侧第一个正数的位置
        int[] nextPos = new int[n];
        int lastPositiveIndex = n; // 用 n 代表无穷大（没找到）
        for (int i = n - 1; i >= 0; i--) {
            if (reds[i] > 0) {
                lastPositiveIndex = i;
            }
            nextPos[i] = lastPositiveIndex;
        }

        // 3. 预处理 suffixCount 数组：统计合法的第三段数量
        // suffixCount[j] 表示以 j 作为第三段的起点，有多少种合法方案
        int[] suffixCount = new int[n + 1];
        long currentSuffixSum = 0;
        boolean suffixHasPos = false;
        
        // 从右向左遍历，j 最小到 2（给第一段和第二段各留至少1个位置）
        for (int j = n - 1; j >= 2; j--) {
            currentSuffixSum += reds[j];
            if (reds[j] > 0) suffixHasPos = true;

            // 继承后面的数量
            suffixCount[j] = suffixCount[j + 1]; 
            // 如果当前后缀满足条件（和为 target 且有正数），数量 +1
            if (currentSuffixSum == target && suffixHasPos) {
                suffixCount[j]++;
            }
        }

        // 4. 从左向右寻找第一段，并累加答案
        long ans = 0;
        long currentPrefixSum = 0;
        boolean prefixHasPos = false;

        // 第一段终点 i 最大到 n-3
        for (int i = 0; i <= n - 3; i++) {
            currentPrefixSum += reds[i];
            if (reds[i] > 0) prefixHasPos = true;

            // 如果找到合法的第一段
            if (currentPrefixSum == target && prefixHasPos) {
                // 中间段从 i+1 开始，找它里面的第一个正数位置 p
                int p = nextPos[i + 1];

                // 如果中间段能找到正数，且不是数组最后一个元素（要给第三段留位置）
                if (p <= n - 2) {
                    // 第三段的起点 j 必须在 p 之后 (即 j >= p + 1)
                    // 这样才能保证索引为 p 的那个正数，稳稳地落在了中间段里！
                    ans += suffixCount[p + 1];
                }
            }
        }

        System.out.println(ans);
    }
}