LeetCode 927. 三等分--双重二分

1. 三等分

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

题解：

如果只给你一个01数组，让你分为两个部分，让这两个部分表示的数字一样，很容易判断吧，直接二分处理找那个分界线，把分成的部分看成A和B，如果A>B，说明左边大了，令r=mid-1;不然令l=mid+1;那么针对这个问题，分成3个部分A、B、C，需要都相等，那么如何处理呢，A=[0,x]，一开始我是暴力枚举x的位置，然后针对区间[x+1,n]进行二分是否存在，这样判断确实没问题，时间复杂度理论上为nlogn也不会超时，一开始是这样写的，但是提交就超时了，最后的几组数据没通过，因为我判断两个区间构成的数字大小关系时是类似于比较字符串大小判断，这个过程也在循环耗时，所以这样就会超时，得更快一点，于是我考虑利用二分找x的位置，其实我一开始也想过这样，但是这样有一个问题，比如我二分了当前x的位置，那么此时针对区间[x+1,n]形成的数字B和C（我写的二分查找函数规定B<=C），和A的关系有3种：

1.A>=B and A>=C

2.A<=B and A<=C

3.A>B and A<C

如果是1的情况，那么我知道此时x取的比较大了，应当r=x-1,如果是2的情况，我知道此时x取比较小了，应当l=x+1,但是如果是3的情况呢？应该怎么调整，此时x是取小了还是取大了，这就是最麻烦的地方，于是我反复考虑这个问题，发现非常有趣的地方，就是如果出现3的情况，说明整个数组是没法构成题目所要求的，直接返回两个-1， 为何？简单证明下就是：如果出现3的情况，如果把x右移，那么A会变大，原来的B已经小于了A，A变大后依然大于B，所以不符合题目要求，如果把x左移，原来的C已经大于A，左移后A变小，C会更大于A，不符合要求，错误，所以出现3的情况直接返回-1。

AC代码

class Solution {
public:
    int check(vector<int>&A,int s1,int t1,int s2,int t2)//比较两个子数组大小
    {
        while(s1<t1&&A[s1]==0)
        s1++;
        while(s2<t2&&A[s2]==0)
        s2++;
        if(t1-s1<t2-s2)return -1;
        if(t1-s1>t2-s2)return 1;
        while(s1<t1)
        {
            if(A[s1]>A[s2])return 1;
            if(A[s1]<A[s2])return -1;
            s1++;
            s2++;
        }
        return 0;
    }
    int fin(vector<int>& A,int st)//二分找B和C
    {
        int l=st,r=A.size()-1,res=-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(A,st,mid,mid+1,A.size()-1)<=0)
            {
                l=mid+1;
                res=mid;
            }
            else r=mid-1;
        }
        return res;//[0,res]为B，[res+1,n]为C
    }
    vector<int> threeEqualParts(vector<int>& A) 
    {
        vector<int>re;
        re.push_back(-1);
        re.push_back(-1);
        int l=0,r=A.size()-3;
        while(l<=r)
        {
            int mid=(l+r)/2;
            int res=fin(A,mid+1);
            int a=check(A,0,mid,mid+1,res);//A-B
            int b=check(A,0,mid,res+1,A.size()-1);//A-C
            if(a==0&&b==0)
            {
                re[0]=mid;
                re[1]=res+1;
                break;
            }
            if(a<=0&&b<=0)
            {
                l=mid+1;
            }
            else if(a>=0&&b>=0)
            {
                r=mid-1;
            }
            else break;
        }
        return re;
    }
};