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;
    }
};