题解 | 喜欢切数组的红

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }

        System.out.println(countValidSplits(nums));
    }

    public static int countValidSplits(int[] nums) {
        int n = nums.length;
        int[] presum = new int[n];      // 前缀和
        int[] posCount = new int[n];    // 正数前缀计数
        int totalSum = 0, posTotal = 0;

        // 计算前缀和和正数个数
        for (int i = 0; i < n; i++) {
            totalSum += nums[i];
            posTotal += (nums[i] > 0) ? 1 : 0;
            presum[i] = totalSum;
            posCount[i] = posTotal;
        }

        // 总和必须是3的倍数，否则无法划分
        if (totalSum % 3 != 0) return 0;
        int targetSum = totalSum / 3;

        int count = 0;
        HashSet<Integer> firstCuts = new HashSet();

        // 枚举右切割点 j，提前存储满足条件的左切割点 i
        for (int j = 1; j < n - 1; j++) {
            // 先存储左侧的可能分割点 i
            if (presum[j - 1] == targetSum && posCount[j - 1] > 0) {
                //map: 左分割点及其数量
                firstCuts.add(j-1);
            }

            // 检查是否有 i，使得 i < j 并满足条件
           //三段之和是3 * targetSum,只要前缀和是2倍，剩下的一段一定是targetSum
            if (presum[j] == 2 * targetSum && posCount[j] > 0) {
                for (Integer i : firstCuts) {
                    if (posCount[j] - posCount[i] > 0) {
                        count += 1;
                    }
                }
            }
        }

        return count;
    }
}

三段相等，那么总和必须是3的倍数。找切点：

1. 计算前缀和： 左切点是一倍，右切点是两倍。
2. 找到后如何配对左右切点构成一个方案？ 针对一个右切点，可能有多个左切点