Ways to Split Array Into Three Subarrays

给一个数组, 求分成三份, 前一份小于等于后一份的分法有几种.

这个题开始的时候以为是dp, 后来想了想用presum也能做, 但是答案用的是二叉搜索, 我看了眼答案, 感觉面试不太容易想到这个优化.

class Solution {
    public int waysToSplit(int[] nums) {
        int n = nums.length;
        int MOD = 1000_000_007;
        int[] pre = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + nums[i - 1];
        }
        int res = 0;
        for(int i = 0; i < n - 1; i++) {
            for(int j = i + 2; j <= n; j++) {
                int left = pre[i + 1] - pre[0];
                int mid = pre[j] - pre[i+1];
                int right = pre[n] - pre[j];
                if(left <= mid && mid <= right)
                    res++;
                res %= MOD;
            }
        }
        return res;
    }
}