LeetCode之Arithmetic Slices II - Subsequence（Kotlin）

问题：

Example:

Input: [2, 4, 6, 8, 10]

Output: 7

Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

方法： 这道题只能自己悟......，DFS好理解但会超时

具体实现：

class ArithmeticSlicesIISubsequence {

    fun numberOfArithmeticSlices(A: IntArray): Int {
        var result = 0
        val cnt = Array(A.size, { mutableMapOf<Int, Int>()})
        for (i in A.indices) {
            for (j in 0 until i) {
                val delta = A[i].toLong() - A[j].toLong()
                if (delta < Integer.MIN_VALUE || delta > Integer.MAX_VALUE) {
                    continue
                }
                val diff = delta.toInt()
                val sum = cnt[j].getOrDefault(diff, 0)
                val origin = cnt[i].getOrDefault(diff, 0)
                cnt[i].put(delta.toInt(), origin + sum + 1)
                result += sum
            }
        }
        return result
    }
}

fun main(args: Array<String>) {
    val input = intArrayOf(2,2,3,3,4,5)
    val arithmeticSlicesIISubsequence = ArithmeticSlicesIISubsequence()
    println(arithmeticSlicesIISubsequence.numberOfArithmeticSlices(input))
}

有问题随时沟通

具体代码实现可以参考Github