| 12
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 
 | class Solution {public:
 vector<int> threeEqualParts(vector<int>& arr) {
 int sum = countOne(arr);
 int len = arr.size();
 if(sum % 3 != 0) {
 return {-1,-1};
 }
 if(sum == 0) {
 return {0, len -1};
 }
 
 int p1,p2,p3;
 p1 = p2 = p3 = 0;
 int i = 0;
 int cur = 0;
 while(i < len) {
 if(arr[i] == 1) {
 if(cur == 0) {
 p1 = i;
 } else if(cur == sum/3) {
 p2 = i;
 } else if(cur == 2*sum/3) {
 p3 = i;
 }
 cur++;
 }
 i++;
 }
 
 int x = p1,y = p2,z = p3;
 int farclen = len - p3;
 if(p1 + farclen > p2 || p2 + farclen > p3) {
 return {-1, -1};
 }
 while(x < p2 && y < p3 && z < len) {
 if(arr[x] != arr[y] || arr[y] != arr[z]) {
 return {-1, -1};
 }
 x++;y++;z++;
 }
 
 return {p1+farclen-1, p2+farclen};
 }
 int
 countOne(vector<int>& arr) {
 int count = 0;
 for(int a : arr) {
 count += a;
 }
 return count;
 }
 };
 
 
 | 
难,看懂解析思路后才写出来的
刚开始的思路是找0,把1分成了n段,取n/3 , 2n/3和 n段后面的0,然后向右移动双指针比较
后来发现有超级长的输入,超时了
解析的思路与我刚好相反,先数1的个数,如果是0或者不能被3整除,说明不能分成三段
1的个数为n,找到第0 n/3 2n/3个1,记为p1, p2, p3
p3到后末尾的长度就是三个子串的长度,如果p1 或 p2 + 字串长度分别大于p2 p3,说明无解
然后向后比较,若后面的数完全相同则有解