难度: Medium
我们称一个分割整数数组的方案是 好的 ，当它满足：
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运行时间: 124 ms
内存: 27.2 MB
class Solution:
def waysToSplit(self, nums: List[int]) -> int:
ans = 0
total = sum(nums)
left_min = left_max = 0
sum_left_min = sum_left_max = sum_right = nums[0]
for right in range(1, len(nums)-1):
sum_right += nums[right]
if 3 * sum_right > 2 * total:
break
while sum_left_min < 2 * sum_right - total:
left_min += 1
sum_left_min += nums[left_min]
while left_max < right and 2 * sum_left_max <= sum_right:
left_max += 1
sum_left_max += nums[left_max]
ans += left_max - left_min
return ans % (10**9+7)
本题解采用前缀和和双指针策略来解决问题。首先计算数组的总和total，然后遍历数组以确定合适的right分界点。对于每一个right，使用两个指针left_min和left_max来确定可能的左区间的范围。left_min是使得left区间的和最小但仍满足left区间的和小于等于mid区间的和的位置，left_max则是left区间和可以达到的最大位置，同时满足left区间的和小于等于mid区间的和的条件。如果left_min到left_max之间有合法的位置，那么这些位置都可以作为合法的分割方案。最后，所有满足条件的分割方法的数量需要对109+7取模。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def waysToSplit(self, nums: List[int]) -> int:
ans = 0 # 初始化方案数
total = sum(nums) # 计算数组总和
left_min = left_max = 0 # 初始化左边界的最小和最大索引
sum_left_min = sum_left_max = sum_right = nums[0] # 初始化左边界和右边界的前缀和
for right in range(1, len(nums)-1):
sum_right += nums[right] # 更新右边界前缀和
if 3 * sum_right > 2 * total: # 判断是否继续循环的条件
break
while sum_left_min < 2 * sum_right - total: # 调整left_min直到满足条件
left_min += 1
sum_left_min += nums[left_min]
while left_max < right and 2 * sum_left_max <= sum_right: # 调整left_max直到满足条件
left_max += 1
sum_left_max += nums[left_max]
ans += left_max - left_min # 计算当前right下的合法分割方案数量
return ans % (10**9+7) # 对结果取模
这个条件是基于数组总和分配的逻辑。在分割数组时，为了确保每个子数组至少有元素，每个子数组的和需要满足一定的条件。特别是，当我们考虑到第三个子数组（即从right到数组末尾的部分）时，这部分的和至少应该不小于第二个子数组的和。如果`3 * sum_right > 2 * total`，这意味着sum_right的三倍已经超过了total的两倍，从而使得第三部分的和超过了前两部分的和的一半，这使得不可能再均等地将剩余部分分配给第二和第三个子数组。因此，这个条件作为循环的终止条件，可以有效地避免不必要的计算，同时确保不遗漏可能的有效分割方案。
在算法中，left_min和left_max的调整是通过两个循环来实现的，确保了每次调整后left区间的和都满足与中间区间和的比较条件。具体而言，对于left_min的调整，通过增加left_min的索引直到`sum_left_min >= 2 * sum_right - total`，这保证了left区间的和不会过大，从而满足left区间和小于等于mid区间和的条件。对于left_max的调整，则是增加left_max的索引，直到`2 * sum_left_max <= sum_right`，确保left区间的和始终小于或等于mid区间的和的一半。这两个循环的控制条件都是精心设计的，确保了在每一步迭代中都不会违反left区间和小于等于mid区间和的原则。
使用`2 * sum_left_max <= sum_right`作为条件，是为了确保left区间的和是mid区间和的一半或更少。这是因为，为了满足题目的要求，确保每个分割后的三个子数组的和都应该相近，左边区间的和不应该大于中间区间。如果使用sum_left_max直接和sum_right比较，可能会导致left区间的和超过mid区间的和，从而不满足题目条件。而`2 * sum_left_max <= sum_right`这个条件则是一个更为严格的限制，可以更安全地保证每个子数组的和的平衡。