三等分

标签：arr partial cur third int sum 三等分

将数组分为三个部分，每部分对应二进制数值相同

1. 三指针

各部分1的数目应当相同，借助这个性质来找三个指针的起始位置
根据最后一个指针起始位置确定串的长度，逐位比较即可

class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        int sum = accumulate(arr.begin(), arr.end(), 0);
        if (sum % 3 != 0)  return {-1, -1};//无法划分
        if (sum == 0) return {0, 2}; //任意划分

        int partial = sum / 3; //每个区域累计1的数目
        int first = 0, second = 0, third = 0, cur = 0;
        for (int i = 0; i < arr.size(); i++) { //去掉前导0
            if (arr[i] == 1) { //累计1的数目
                if (cur == 0) first = i;
                else if (cur == partial) second = i;
                else if (cur == 2 * partial) third = i;
                cur++;
            }
        }

        int len = (int)arr.size() - third;//第三个部分长度
        if (first + len <= second && second + len <= third) {//去除前导0后，前面应该有足够的余量，最后三个串长度一致
            int i = 0;
            while (third + i < arr.size()) {
                if (arr[first + i] != arr[second + i] || arr[first + i] != arr[third + i]) //同时比较对应位置
                    return {-1, -1};
                i++;
            }
            return {first + len - 1, second + len};
        }
        return {-1, -1};
    }
};

标签：arr,partial,cur,third,int,sum,三等分
From： https://www.cnblogs.com/929code/p/17429250.html