leetcode 困难题 927. Three Equal Parts 三等分-耗时100

Problem: 927. Three Equal Parts 三等分

耗时100%，可能存在前置0，所以逆向思考的，首先统计0、1频次，若1的个数不能被3整除则不可能返回-1，若没有1则返回{0, n-1}，每个二进制数字的1的个数都是ch[1]/3，逆向考虑的话，最后一个二进制数字不需要考虑前置0，只需要数1个数就行了，所以拼接字符串当third == avg时退出，然后反转字符串tg3

再考虑第一个二进制数字，从1开始略过前置0，拼接字符串，若tg1==tg3则退出，最后考虑第二个二进制数字，也是忽略前置0拼接字符串，若和tg3相同则返回结果，否则返回-1

Code

class Solution { public: vector<int> threeEqualParts(vector<int>& arr) { int ch[2] = {0, 0}, n = arr.size(); for(int& i : arr) ch[i]++; int avg = ch[1] / 3; if(ch[1]%3!=0) return {-1, -1}; if(ch[1] == 0) return {0, n - 1}; int third = 0, ii, jj; string tg3, tg1, tg2; for(int i = n - 1; i >= 0; i--) { if( arr[i] == 1 ) third++; tg3 += (arr[i] + '0'); if(third == avg) { jj = i; break; } } reverse(tg3.begin(), tg3.end()); int l = 0; while(l < jj && arr[l]==0) l++; for(int i = l; i < jj; i++) { tg1 += (arr[i] + '0'); if(tg1 == tg3) { ii = i; break; } } l = ii + 1; while(l < jj && arr[l]==0) l++; for(int i = l; i < jj; i++) { tg2 += (arr[i] + '0'); if(tg2 == tg3) { jj = i + 1; return {ii, jj}; } } return {-1, -1}; } };