Leetcode 1013.将数组分成和相等的三个部分【C++】

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

题目

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

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

示例 1：

输出：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

示例 2：

输入：[0,2,1,-6,6,7,9,-1,2,0,1]
输出：false

示例 3：

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

提示：

• 3 <= A.length <= 50000
• -10^4 <= A[i] <= 10^4

解题思路

这个题不难，首先需要明白的是，如果一个数组能如题述那样分成三等分，那么这三个和相等，并且三个等分的和相加即为整个数组所有元素的和。

求整个数组的和 sum 是很简单的，如果这个数组能三等分则每个等分的和即为 sum/3 ，所以我们只需要遍历数组，逐个元素相加求和 sumOfPart，一旦 sumOfPart == sum / 3 则说明找到了一个等分，此时将 sumOfPart 重置为0（以开始计算新的一部分的部分和），并将 part++ 表示新找到了一个等分。

特别需要注意的是，当 sum == 0 的时候，sumOfPart == 0 是可能存在多个部分的，即 part >= 3，但不能小于3，因为至少需要三等分。

代码

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& A) {
        //计算整个数组的和
        int sum = 0;
        for (auto a : A) {
            sum += a;
        }
        int part = 0;//计数和为sum/3的分组数
        int sumOfPart = 0;//部分和
        for (auto a : A) {
            sumOfPart += a;
            if (sumOfPart == sum / 3) {
                sumOfPart = 0;//将部分和重置为0
                part++;//组数+1
            }
        }
        //当sum==0的时候part存在大于3的情况,但不可能小于3
        return part >= 3 ? true : false;
    }
};