413. Arithmetic Slices

[antop-dev]

https://leetcode.com/problems/arithmetic-slices/

[antop-dev]

점화식 : i번째를 기준으로 nums[i - 2] ~ nums[i - 1] - nums[i] 사이의 값이 값으면 dp[i] = 1 + dp[i - 1]

• 시간 복잡도 : O(n)
• 공간 복잡도 : O(n)

class Solution {
    fun numberOfArithmeticSlices(nums: IntArray): Int {
        if (nums.size < 3) return 0
        val dp = IntArray(nums.size)

        var ans = 0
        for (i in 2 until dp.size) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                dp[i] = 1 + dp[i - 1]
            }
            ans += dp[i]
        }
        return ans
    }
}