題目

給定一個(gè)由 0 和 1 組成的數(shù)組 A，將數(shù)組分成 3 個(gè)非空的部分，使得所有這些部分表示相同的二進(jìn)制值。

如果可以做到，請(qǐng)返回任何 [i, j]，其中 i+1 < j，這樣一來(lái)：

A[0], A[1], ..., A[i] 組成第一部分；
A[i+1], A[i+2], ..., A[j-1] 作為第二部分；
A[j], A[j+1], ..., A[A.length - 1] 是第三部分。
這三個(gè)部分所表示的二進(jìn)制值相等。
如果無(wú)法做到，就返回 [-1, -1]。

注意，在考慮每個(gè)部分所表示的二進(jìn)制時(shí)，應(yīng)當(dāng)將其看作一個(gè)整體。例如，[1,1,0] 表示十進(jìn)制中的 6，而不會(huì)是 3。此外，前導(dǎo)零也是被允許的，所以 [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

思路

有幾個(gè)不太容易一眼就發(fā)現(xiàn)的小tips

• 分為三等份的相同值，其 ‘1’ 的個(gè)數(shù)應(yīng)該是相同的，也就是說(shuō)，在給定的數(shù)組中，’1‘ 的個(gè)數(shù)應(yīng)該可以 % 3 == 0，否則無(wú)法分為三等份?？梢苑譃槿确莸拿恳环葜小?‘的個(gè)數(shù)應(yīng)該是數(shù)組中’1‘的個(gè)數(shù)除三。
• 知道‘1’的個(gè)數(shù)以后，我們可以確定下來(lái)每一份的值，該值是唯一的，可以通過(guò)最后一份來(lái)求出：從后往前遍歷數(shù)組，直到‘1’的個(gè)數(shù)等于數(shù)組中‘1’的個(gè)數(shù)除三，該二進(jìn)制數(shù)就是每一份的值。（該過(guò)程可以保留后綴的‘0’的數(shù)量以備后面用到）
• 確定值后，可以從前向后遍歷數(shù)組，同樣通過(guò)‘1’的個(gè)數(shù)找數(shù)，‘1’的個(gè)數(shù)找齊后，加上剛才求出后綴0，如果后面的0的數(shù)量沒(méi)有求出的后綴0多，則無(wú)法分割。若有，求這個(gè)二進(jìn)制數(shù)的值，等于之前求出的值，則這個(gè)位置就是i 的值，若不像等，則無(wú)法分割。重復(fù)該步驟可以得到j(luò) 的值。

該方法的時(shí)間復(fù)雜度為O(n)，如果大家有更優(yōu)秀的解決辦法，或者可以?xún)?yōu)化的地方，歡迎留言。

code

func threeEqualParts(A []int) []int {
    var lA = len(A) -1
    result := make([]int,0,2)
    ones := 0
    for _, a := range A {
        if a == 1 {
            ones++
        }
    }
    if ones % 3 != 0{
        result = append(result, -1, -1)
        return result
    }
    
    partOnes := ones / 3
    if partOnes == 0 {
        result = append(result, 0, 4)
        return result
    }
    tPartOnes := partOnes
    suffixZero := 0
    flag := false
    realValue := 0
    var tmpI, tmpJ int
    
    for i:=lA;i>0;i-- {
        // 確定真值 suffixZero
        if !flag && A[i] == 0{
            suffixZero++
        }
        if A[i] == 1 {
            flag = true
            tPartOnes--
            if tPartOnes == 0{
                realValue = cal(A[i:])
                tmpJ = i
                break
            }
        }   
    }
    
    
    tmpI,ok := find(A[:tmpJ], partOnes, realValue, suffixZero)
    if ! ok {
        result = append(result, -1, -1)
        return result
    }
    tmpJ, ok = find(A[tmpI+1:tmpJ], partOnes, realValue, suffixZero)
    if ! ok {
        result = append(result, -1, -1)
        return result
    }
    tmpJ = tmpI+tmpJ+2
    
    result = append(result, tmpI, tmpJ)
    return result
    
}

// 用來(lái)找 1、2 部分，從前找，找到就返回當(dāng)前位置
func find(A []int, partOnes, realValue, suffixZero int) (i int, b bool) {
    l := len(A) -1
    tmpI:=0
    for i, a := range A {
        if a == 1 {
            partOnes--
            if partOnes==0{
                for j:=suffixZero;j>0;j--{
                    if i+j > l {
                        return 0, false
                    }
                    if A[i+j] != 0{
                        return 0, false
                    }
                }
                tmpI = i+suffixZero
                break
            }
        }
    }
    
    if cal(A[:tmpI+1]) != realValue {
        return 0, false
    }
    return tmpI, true
}

func cal(A []int) int {
    l := len(A)
    result := 0
    for i, a := range A {
        result += a * ((l-i) * (l-i))
    }
    return result
}