题目描述
我们称一个分割整数数组的方案是 好的,当它满足:
- 数组被分成三个 非空 连续子数组,从左至右分别命名为
left
,mid
,right
。 left
中元素和小于等于mid
中元素和,mid
中元素和小于等于right
中元素和。
给定一个 非负 整数数组 nums
,请你返回 好的 分割 nums
方案数目。由于答案可能会很大,请你将结果对 10^9 + 7
取余后返回。
样例
输入:nums = [1,1,1]
输出:1
解释:唯一一种好的分割方案是将 nums 分成 [1] [1] [1]。
输入:nums = [1,2,2,2,5,0]
输出:3
解释:nums 总共有 3 种好的分割方案:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]
输入:nums = [3,2,1]
输出:0
解释:没有好的分割方案。
限制
3 <= nums.length <= 10^5
0 <= nums[i] <= 10^4
算法
(前缀和、双指针) $O(n)$
- 求出原数组的前缀和数组。
- 对于每个给定的第二分割点 $i$,找到第一分割点的上下界 $l$ 和 $r$,使得根据在第一分割点范围内的点都满足条件。
- 注意到,第一分割点的下界控制 $mid \le right$,上界控制 $left \le mid$,且上下界都是随着 $i$ 单调不减的,故可以使用双指针维护。
时间复杂度
- 预处理的时间复杂度为 $O(n)$。
- 统计答案的时间复杂度为 $O(n)$。
- 故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储前缀和数组。
- 可以通过动态维护部分和,优化掉前缀和数组,使空间复杂度降为常数。
C++ 代码
class Solution {
public:
int waysToSplit(vector<int>& nums) {
const int n = nums.size();
vector<int> sum(n + 1, 0);
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + nums[i - 1];
const int mod = 1000000007;
int ans = 0;
for (int i = 3, r = 2, l = 2; i <= n; i++) {
while (r < i && sum[r - 1] <= sum[i - 1] - sum[r - 1]) r++;
while (l < i && sum[i - 1] - sum[l - 1] > sum[n] - sum[i - 1]) l++;
ans = (ans + max(0, r - l)) % mod;
}
return ans;
}
};