【专题篇 - Day 64】 2021-01-041712. 将数组分成三个子数组的方案数（01. 二分法 ）
题目描述
入选理由
- 周赛题目，新鲜出炉
- 这道题是另外一种典型类型，即前缀和二分。这在讲义中是没有的。由于前缀和是单调不严格递增的，因此其天生就和二分有关联。接下来，我们还会介绍一种常见二分题型。
题目描述
我们称一个分割整数数组的方案是 好的 ，当它满足：
数组被分成三个 非空 连续子数组，从左至右分别命名为 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 ⇐ 105
0 ⇐ nums[i] ⇐ 104来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ways-to-split-array-into-three-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我的回答
解法一
时空复杂度
时间复杂度：O(n)
空间复杂度: O(1)