题解 | 喜欢切数组的红

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class HJ98 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            System.out.println(f3(arr));
        }
    }
    
    private static int f3(int[] arr) {
        // 求和，无法整除3则不符合要求
        int sum = Arrays.stream(arr).sum();
        if (sum % 3 != 0) {
            return 0;
        }

        // 从左边遍历，记录能求和得到 sum/3的下标
        int sum1 = 0;
        boolean hasPosInt1 = false;
        List<Integer> indexList1 = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            sum1 += arr[i];
            hasPosInt1 = hasPosInt1 || arr[i] > 0;
            if (hasPosInt1 && sum1 == sum / 3) {
                indexList1.add(i);
            }
        }

        // 从右边遍历，记录能求和得到 sum/3的下标
        int sum2 = 0;
        boolean hasPosInt2 = false;
        List<Integer> indexList2 = new ArrayList<>();
        for (int i = arr.length - 1; i >= 0; i--) {
            sum2 += arr[i];
            hasPosInt2 = hasPosInt2 || arr[i] > 0;
            if (hasPosInt2 && sum2 == sum / 3) {
                indexList2.add(i);
            }
        }

        // 遍历左下标
        int count = 0;
        for (int i = 0; i < indexList1.size(); i++) {
            // 左下标
            Integer index1 = indexList1.get(i);

            // 记录选中左下标时，右下标有多少种可选方案
            int count1 = 0;

            // 遍历右下标
            for (int j = 0; j < indexList2.size(); j++) {
                Integer index2 = indexList2.get(j);
                // 数组2是从大到小排序的，如果index2 <= index1，则后面的也是一样，可以直接break
                if (index2 <= index1) {
                    break;
                }

                // index1 - index2之间的数据，排查是否有正数
                boolean hasPosInt3 = false;
                for (int k = index1 + 1; k < index2; k++) {
                    if ( arr[k] > 0) {
                        hasPosInt3 = true;
                        break;
                    }
                }
                if (hasPosInt3) {
                    count1 = j + 1;
                }
            }
            count += count1;
        }

        return count;
    }
}