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;
}
}