题目描述

给定一个只含 0 和 1 的数组 A，将这个数组分成 3 个非空的部分，使得每一部分代表相同的二进制的值。

如果可分，返回任意的[i, j]，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, -1]。

注意，当考虑二进制的值时，整个部分都需要用到。例如，[1,1,0] 代表十进制的 6，非 3。另外，允许前导零，所以 [0,1,1] 和 [1,1] 表示相同的值。

样例

输入: [1,0,1,0,1]
输出: [0,3]

输入: [1,1,0,1,1]
输出: [-1,-1]

算法

(模拟) $O(n)$

1. 所有三部分拥有相同的 1 的个数，所以先统计 1 的个数。如果个数不被三整除，则则不可能。
2. 如果 1 的个数为 0，则直接返回 [0, 2]。
3. 否则，找到每一部分开头的 1 和 末尾的 1 所在的位置。例如 [0, 0, 1, 1, 0, 1, 1, 1, 1, 0]，三部分的位置分别为 (2, 3), (5, 6), (7, 8)；
4. 判断每个区间长度是否一致；不一致则不可能。
5. 检查每个区间内部的 01 子串是否一致；不一致则不可能。
6. 记录最后一部分中，最后的 1 和数组末尾的距离，即为 last_zero，这个值决定了每一部分最后需要多少个 0。
7. 最后判断前两个部分中，末尾是否足够有 last_zero 个 0。

时间复杂度

• 线性遍历若干次数组，故时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    vector<int> threeEqualParts(vector<int>& A) {
        int n = A.size(), ones = 0;
        for (int i = 0; i < n; i++)
            if (A[i] == 1)
                ones++;

        if (ones % 3 != 0)
            return {-1, -1};

        if (ones == 0)
            return {0, 2};

        ones /= 3;

        int s[3], t[3];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (A[i] == 1) {
                cnt++;
                if (ones == 1)
                    s[cnt / ones - 1] = i;
                if (cnt % ones == 1)
                    s[cnt / ones] = i;

                if (cnt % ones == 0)
                    t[cnt / ones - 1] = i;
            }
        }


        int len = t[0] - s[0] + 1;
        if (t[1] - s[1] + 1!= len || t[2] - s[2] + 1!= len)
            return {-1, -1};

        for (int i = 0; i < len; i++) {
            int x = A[i + s[0]];
            if (x != A[i + s[1]] || x != A[i + s[2]])
                return {-1, -1};
        }

        int last_zeros = n - t[2] - 1;

        if (s[2] - t[1] - 1 < last_zeros || s[1] - t[0] - 1 < last_zeros)
            return {-1, -1};

        return {t[0] + last_zeros, t[1] + last_zeros + 1};
    }
};