阅读 26

LeetCode之Partition Array Into Three Parts With Equal Sum(Kotlin)

问题:


方法: 一上来很容易陷入暴力法的误区。其实如果数组存在三部分等值则首先可以求解出相等的值是多少,然后遍历数组,当和为相等值时计数1,并将和归零,最后当计数次数等于3时则数组存在三部分相等的情况。其中相等的值是0时比较特殊,计数大于3即可。

class PartitionArrayIntoThreePartsWithEqualSum {
    fun canThreePartsEqualSum(A: IntArray): Boolean {
        if (A.sum() % 3 != 0) {
            return false
        }
        val avg = A.sum() / 3
        var sum = 0
        var times = 0
        for (num in A) {
            sum += num
            if (sum == avg) {
                sum = 0
                times++
            }
        }
        return times == 3 || (times > 3 && avg == 0)
    }
}

fun main(args: Array<String>) {
    val input = intArrayOf(10, -10, 10, -10, 10, -10, 10, -10)
    val partitionArrayIntoThreePartsWithEqualSum = PartitionArrayIntoThreePartsWithEqualSum()
    partitionArrayIntoThreePartsWithEqualSum.canThreePartsEqualSum(input)
}
复制代码

有问题随时沟通

具体代码实现可以参考Github