# 1013. Partition Array Into Three Parts With Equal Sum

Given an array of integers `arr`, return `true` 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 `i + 1 < j` with `(arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])`

Example 1:

``````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
``````

Example 2:

``````Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false
``````

Example 3:

``````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
``````

Constraints:

• `3 <= arr.length <= 5 * 104`
• `-104 <= arr[i] <= 104`

``````class Solution {
public:
bool canThreePartsEqualSum(vector<int>& arr) {
int sum = accumulate(arr.begin(), arr.end(), 0);
if (sum % 3 != 0) return false;
int target = sum / 3, cur = 0, cnt = 0;
for (int num : arr) {
cur += num;
if (cur == target) {
++cnt;
cur = 0;
}
}
return cnt >= 3;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1013

https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/

https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/discuss/260885/C%2B%2B-6-lines-O(n)-target-sum

https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/discuss/260895/JavaPython-3-two-O(n)-time-O(1)-space-codes-w-brief-explanation-and-analysis.

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation