927. 三等分

[MyLinChi]

问题

给定一个由 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：

输入：[1,0,1,0,1]
输出：[0,3]
示例 2：

输出：[1,1,0,1,1]
输出：[-1,-1]
 

提示：

3 <= A.length <= 30000
A[i] == 0 或 A[i] == 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/three-equal-parts
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

求解

先算出数组中1的个数，然后对这些1进行三等分，考虑后置零时根据第3部分决定后置零的个数。

class Solution {
private:
    vector<int> A;
    bool equ(int a, int b, int c, int d) {
        if ((b - a) != (d - c))return false;
        for (int i = a, j = c;i <= b;++i, ++j) {
            if (A[i] != A[j])return false;
        }
        return true;
    }
public:
    vector<int> threeEqualParts(vector<int>& A) {
        int sum = 0;
        int len = A.size();
        this->A = A;
        vector<int> res = { -1,-1 };
        for (int i = 0;i < len;sum += A[i++]);
        if (sum % 3 != 0)return res;
        int sth = sum / 3;
        if (sth == 0) {
            if (len >= 3) {
                res[0] = 0;
                res[1] = len - 1;
            }
            return res;
        }
        int onel, oner, twol, twor, threel, threer;
        int cnt = 0;
        for (int i = 0;i < len;++i) {
            if (A[i] == 1) {
                ++cnt;
                if (cnt == 1) {
                    onel = i;
                }
                if (cnt == sth) {
                    oner = i;
                }
                if (cnt == sth + 1) {
                    twol = i;
                }
                if (cnt == 2 * sth) {
                    twor = i;
                }
                if (cnt == 2 * sth + 1) {
                    threel = i;
                }
                if (cnt == 3 * sth) {
                    threer = i;
                }
            }
        }
        
        //if the three intervals aren't equal 
        if (!equ(onel, oner, threel, threer) || !equ(twol, twor, threel, threer)) {
            return res;
        }
        int x = twol - oner - 1;
        int y = threel - twor - 1;
        int z = len - threer - 1;
        if (x < z || y < z)return res;
        res[0] = oner + z;
        res[1] = twor + z + 1;
        return res;
    }
};