partition-array-into-three-parts-with-equal-sum

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an array of integers <code>arr</code>, return <code>true</code> if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes <code>i + 1 &lt; j</code> with <code>(arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])</code>

&nbsp;
Example 1:

<pre>
Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
</pre>

Example 2:

<pre>
Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false
</pre>

Example 3:

<pre>
Input: arr = [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>3 &lt;= arr.length &lt;= 5 * 104</code></li>
	<li><code>-104 &lt;= arr[i] &lt;= 104</code></li>
</ul>

canThreePartsEqualSum

Partition Array Into Three Parts With Equal Sum

Find the Middle Index in Array

find-the-middle-index-in-array

找到数组的中间位置

Greedy

Array

给你一个整数数组 <code>arr</code>，只有可以将其划分为三个和相等的 非空 部分时才返回 <code>true</code>，否则返回 <code>false</code>。

形式上，如果可以找出索引 <code>i + 1 < j</code> 且满足 <code>(arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])</code> 就可以将数组三等分。

 

示例 1：

<pre>
输入：arr = [0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
</pre>

示例 2：

<pre>
输入：arr = [0,2,1,-6,6,7,9,-1,2,0,1]
输出：false
</pre>

示例 3：

<pre>
输入：arr = [3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
</pre>

 

提示：

<ul>
	<li><code>3 <= arr.length <= 5 * 104</code></li>
	<li><code>-104 <= arr[i] <= 104</code></li>
</ul>