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

这道题给了我们一个数组,问能不能将该数组分成非空的三个部分,且每个部分的和相同。其实就是分成三个子数组,既然每个部分的和相同,说明数组的数字总和一定是3的倍数,若不是,则一定无法分。先求出数组的数字之和,除以3就是每个部分之和 target,然后进行数组的遍历,用一个变量 cur 来累积当前和,cnt 来表示已经成功分割的部分。每次累加到 target 的时候,cnt 自增1,且 cur 清零0,最终只要 cnt 的个数大于等于3就可以返回 true。可能有的小朋友会问,为啥会出现大于3的情况,这是因为当 target 为0的时候,多个为0的子数组可以合并成为一个为0的子数组,比如 [10,-10,10,-10,10,-10,10,-10],前四个数字组成一个为0的部分,后面四个数字分别组成两个为0的部分,还是符合题意的,参见代码如下:

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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation