ways-to-split-array-into-three-subarrays

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

A split of an integer array is good if:

<ul>
	<li>The array is split into three non-empty contiguous subarrays - named <code>left</code>, <code>mid</code>, <code>right</code> respectively from left to right.</li>
	<li>The sum of the elements in <code>left</code> is less than or equal to the sum of the elements in <code>mid</code>, and the sum of the elements in <code>mid</code> is less than or equal to the sum of the elements in <code>right</code>.</li>
</ul>

Given <code>nums</code>, an array of non-negative integers, return the number of good ways to split <code>nums</code>. As the number may be too large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<pre>
Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].</pre>

Example 2:

<pre>
Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]
</pre>

Example 3:

<pre>
Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>3 &lt;= nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 104</code></li>
</ul>

第 222 场周赛

weekly-contest-222

waysToSplit

Ways to Split Array Into Three Subarrays

Number of Ways to Divide a Long Corridor

number-of-ways-to-divide-a-long-corridor

分隔长廊的方案数

Number of Ways to Split Array

number-of-ways-to-split-array

分割数组的方案数

Array

Two Pointers

Binary Search

Prefix Sum

我们称一个分割整数数组的方案是 好的 ，当它满足：

<ul>
	<li>数组被分成三个 非空 连续子数组，从左至右分别命名为 <code>left</code> ， <code>mid</code> ， <code>right</code> 。</li>
	<li><code>left</code> 中元素和小于等于 <code>mid</code> 中元素和，<code>mid</code> 中元素和小于等于 <code>right</code> 中元素和。</li>
</ul>

给你一个 非负 整数数组 <code>nums</code> ，请你返回 好的 分割 <code>nums</code> 方案数目。由于答案可能会很大，请你将结果对 <code>109 + 7</code> 取余后返回。

 

示例 1：

<pre>
输入：nums = [1,1,1]
输出：1
解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。</pre>

示例 2：

<pre>
输入：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]
</pre>

示例 3：

<pre>
输入：nums = [3,2,1]
输出：0
解释：没有好的分割方案。</pre>

 

提示：

<ul>
	<li><code>3 <= nums.length <= 105</code></li>
	<li><code>0 <= nums[i] <= 104</code></li>
</ul>