package daily.hard

fun main() {
    // 927. 三等分
    // https://leetcode.cn/problems/three-equal-parts/
    println(threeEqualParts(intArrayOf(0,0,0,0,0)).contentToString())
}

fun threeEqualParts(arr: IntArray): IntArray {

    // 一个满足题意的数组，1 的数量应该是 3 的整数倍，且每一份中，1的数量是一样的
    // 所以可以先计算数组的和，如果不能被 3 整数，那肯定不符合题意
    val sum = arr.sum()
    if (sum % 3 != 0) {
        return intArrayOf(-1, -1)
    }
    // 如果和为0，说明每个元素都是0，也是符合题意的数组
    if (sum == 0) {
        return intArrayOf(0, arr.size - 1)
    }
    // 分成3份，计算每一份中，1的数量
    val partial = sum / 3
    // 找到每一份中，第一个1的下标
    var first = 0
    var second = 0
    var third = 0
    // cur: 1 的下标
    var cur = 0
    for (i in arr.indices) {
        if (arr[i] == 1) {
            if (cur == 0) {
                first = i
            }else if (cur == partial) {
                second = i
            }else if (cur == partial * 2) {
                third = i
            }
            cur++
        }
    }
    // [third, arr.size) 构成了最后一个数，计算二进制数的长度
    val len = arr.size - third
    val firstEnd/**exclude**/ = first + len
    val secondEnd/**exclude**/ = second + len
    if (firstEnd > second || secondEnd > third) {
        // 三个数的二进制数有重合
        // 如：11011110，len = arr.size - third = 8 - 5 = 3
        // first = 0, firstEnd = 3, second = 3, secondEnd = 6, secondEnd > third，第二段和第三段重合了
        return intArrayOf(-1, -1)
    }
    for (i in 0 until len) {
        if (arr[first+i] == arr[second+i] && arr[second+i] == arr[third+i]) {
            if (i == len - 1) {
                // 每一份的最后一个数都一样了，那就是满足题意的
                return intArrayOf(firstEnd-1, secondEnd)
            }
            continue
        }else {
            return intArrayOf(-1, -1)
        }
    }
    return intArrayOf(-1, -1)
}