class Solution {
public:
int waysToSplit(vector<int>& nums) {
}
};
1712. 将数组分成三个子数组的方案数
我们称一个分割整数数组的方案是 好的 ，当它满足：
left ， mid ， right 。left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。给你一个 非负 整数数组 nums ，请你返回 好的 分割 nums 方案数目。由于答案可能会很大，请你将结果对 109 + 7 取余后返回。
示例 1：
输入：nums = [1,1,1] 输出：1 解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。
示例 2：
输入：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]
示例 3：
输入：nums = [3,2,1] 输出：0 解释：没有好的分割方案。
提示：
3 <= nums.length <= 1050 <= nums[i] <= 104原站题解
java 解法, 执行用时: 15 ms, 内存消耗: 55.1 MB, 提交时间: 2023-09-25 15:07:34
class Solution {
public int waysToSplit(int[] nums) {
int n = nums.length;
int[] sum = new int[n + 1]; // 前缀和
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + nums[i - 1];
}
final int MOD = 1000000000 + 7;
long ans = 0;
// |______|________|_______|________|
// 1 i l r n
// i 表示第一刀的位置，枚举第一刀的位置，计算第二刀的可选位置数
for (int i = 1, l = 2, r = 2; i <= n - 1; i++) {
l = Math.max(l, i + 1);
r = Math.max(r, i + 1);
// sum(right) >= sum(mid)，r最大为n-1，right保证要有一个数
while (r <= n - 1 && sum[n] - sum[r] >= sum[r] - sum[i]) {
r++;
}
// sum(mid) >= sum(left)
while (l <= n - 1 && sum[l] - sum[i] < sum[i]) {
l++;
}
if (l <= r) {
ans += r - l;
}
}
return (int) (ans % MOD);
}
}
java 解法, 执行用时: 23 ms, 内存消耗: 55.1 MB, 提交时间: 2023-09-25 15:06:32
class Solution {
public int waysToSplit(int[] nums) {
int n = nums.length;
// 计算前缀和
int[] sums = new int[n];
sums[0] = nums[0];
for (int i = 1; i < n; i++) {
sums[i] = sums[i - 1] + nums[i];
}
final int MOD = 1000000000 + 7;
long ans = 0;
// 第一刀的最大值：sum(nums) / 3
int t = sums[n - 1] / 3;
for (int i = 0; i < n && sums[i] <= t; i++) {
// 二分查找第二刀的最小值：sum(mid) == sum(left)
// 在 [i+1, n] 中二分查找 sums[i] * 2，sums[i] 为到 i 为止元素和，因为是前缀数组，因而应该查找 sum(left) + sum(mid)
int left = lowerBound(i + 1, n - 1, sums, sums[i] * 2);
// 二分查找第二刀的最大值：sum(mid) == sum(mid + right) / 2
// 在 [i+1, n] 中二分查找 sums[i] + (sums[n - 1] - sums[i]) / 2)，因为是前缀数组，因而应该查找 sum(left) + sum(mid + right) / 2
int right = upperBound(i + 1, n - 1, sums, sums[i] + (sums[n - 1] - sums[i]) / 2);
if (right >= left) {
ans += right - left + 1;
}
}
return (int) (ans % MOD);
}
public int lowerBound(int left, int right, int[] nums, int target) {
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
public int upperBound(int left, int right, int[] nums, int target) {
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
}
python3 解法, 执行用时: 692 ms, 内存消耗: 27 MB, 提交时间: 2023-09-25 15:05:30
class Solution:
def waysToSplit(self, nums: List[int]) -> int:
mod = 10**9 + 7
n = len(nums)
pre = list(accumulate(nums))
ans = 0
for i in range(n):
l = max(i+1,bisect_left(pre,pre[i]+pre[i]))
r = min(n-1,bisect_right(pre,(pre[i]+pre[-1])//2))
ans = (ans + max(0,r - l)) % mod
return ans % mod
golang 解法, 执行用时: 144 ms, 内存消耗: 9 MB, 提交时间: 2023-09-25 14:57:33
func waysToSplit(a []int) (ans int) {
n := len(a)
sum := make([]int, n+1)
for i, v := range a {
sum[i+1] = sum[i] + v
}
for r := 2; r < n && 3*sum[r] <= 2*sum[n]; r++ {
l1 := sort.SearchInts(sum[1:r], 2*sum[r]-sum[n]) + 1
ans += sort.SearchInts(sum[l1:r], sum[r]/2+1)
}
return ans % (1e9 + 7)
}