【每日打卡】 [leetcode]1013-将数组分成和相等的三个部分

马谦马谦马谦

615
文章

17
评论

2020 年 3 月 11 日 20:08:50数据结构和算法评论139字数 893阅读 2 分 58 秒阅读模式

来源：力扣（LeetCode）

链接：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，可以直接返回 false，因为输入的都是整数，每一段的和也都是整数。
如果总和能整除 3，从头开始遍历数组，每找到一个满足条件的计数加 1，直到最后如果计数为 3 的话就说明是存在符合条件的区间。

一个需要额外注意的地方是：

【每日打卡】[leetcode]1013-将数组分成和相等的三个部分-图片1

上面的数组中，总和是 0，三个分区间的和也应该是 0 。但是实际上，按照上面的算法，计数为 4，这个场景怎么处理？实际上，只要把最后一个区间归类到第三个区间就可以了，只要他们两者的和满足条件就行了。

【每日打卡】[leetcode]1013-将数组分成和相等的三个部分-图片2

而第三个区间是满足条件的，这种情况下，只要从第四个满足条件的区间开始，后面所有元素的总和不会对第三个区间的和造成影响的时候（即后面所有元素和为 0），数组是满足条件的。

三、代码

class Solution {
public:
    bool canThreePartsEqualSum(vector<int> &A) {
        int i, cnt = 0, sum, tmp_sum, n;
        // 计算所有的总和
        for (auto x: A) {
            cnt += x;
        }

        // 如果总和不能整除 3，直接返回 false
        if (cnt % 3 != 0)
            return false;
        // 计算每一段的和
        sum = cnt / 3;

        // 找到三段符合条件的和
        tmp_sum = 0, n = 0;
        for (i = 0; i < A.size() && n < 3; i++) {
            tmp_sum += A[i];
            if (tmp_sum == sum) {
                // 每找到一段，tmp_sum 置零，重新开始找
                n++;
                tmp_sum = 0;
            }
        }

        // 已经得到了三段满足条件的和，但是数组可能并没有遍历完
        // 只有在剩余元素的总和是 0 的条件下才认为满足条件
        tmp_sum = 0;
        for (; i < A.size(); i++) {
            tmp_sum += A[i];
        }

        return n == 3 && tmp_sum == 0;
    }
};

class Solution {

public:

bool canThreePartsEqualSum(vector<int> &A) {

int i, cnt = 0, sum, tmp_sum, n;

// 计算所有的总和

for (auto x: A) {

cnt += x;

}

// 如果总和不能整除 3，直接返回 false

if (cnt % 3 != 0)

return false;

// 计算每一段的和

sum = cnt / 3;

// 找到三段符合条件的和

tmp_sum = 0, n = 0;

for (i = 0; i < A.size() && n < 3; i++) {

tmp_sum += A[i];

if (tmp_sum == sum) {

// 每找到一段，tmp_sum 置零，重新开始找

n++;

tmp_sum = 0;

}

// 已经得到了三段满足条件的和，但是数组可能并没有遍历完

// 只有在剩余元素的总和是 0 的条件下才认为满足条件

tmp_sum = 0;

for (; i < A.size(); i++) {

tmp_sum += A[i];

}

return n == 3 && tmp_sum == 0;

}

};

复杂度分析

时间复杂度：O(N)
空间复杂度：O(1)

单元测试案例：

TEST(Solution, leetcode_1) {
    Solution s;
    vector<int> v{0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1};
    EXPECT_TRUE(s.canThreePartsEqualSum(v));
}

TEST(Solution, leetcode_2) {
    Solution s;
    vector<int> v{0, 2, 1, -6, 6, 7, 9, -1, 2, 0, 1};
    EXPECT_FALSE(s.canThreePartsEqualSum(v));
}

TEST(Solution, leetcode_3) {
    Solution s;
    vector<int> v{3, 3, 6, 5, -2, 2, 5, 1, -9, 4};
    EXPECT_TRUE(s.canThreePartsEqualSum(v));
}

TEST(Solution, leetcode_4) {
    Solution s;
    vector<int> v{10, -10, 10, -10, 10, -10, 10, -10};
    EXPECT_TRUE(s.canThreePartsEqualSum(v));
}