413.arithmetic-slices.md

413. Arithmetic Slices

Group By Consecutive (Edges)

// Backward
fun numberOfArithmeticSlices(nums: IntArray): Int {
    var i = 1 // Start from 2nd element
    var ans = 0
    val n = nums.size
    while (i < n) { // Iterate from 1 to n - 1
        val diff = nums[i] - nums[i - 1]
        val start = i - 1
        i++
        while (i < n && nums[i] - nums[i - 1] == diff) {
            i++
        }
        val end = i
        val length = end - start
        if (length >= 3) {
            ans += count(length)
        }
    }
    return ans
}

// Forward
fun numberOfArithmeticSlices(nums: IntArray): Int {
    var i = 0
    var ans = 0
    val n = nums.size
    while (i + 1 < n) { // Ieterate from 0 to n - 2
        val diff = nums[i + 1] - nums[i]
        val start = i
        while (i + 1 < n && nums[i + 1] - nums[i] == diff) {
            i++
        }
        val end = i
        val length = end - start + 1
        if (length >= 3) {
            ans += countSubarrays(length)
        }
    }
    return ans
}

/**
 * For normal `N` = (N + 1) * N / 2, but we take at least 3 elements as one subarray, so N' = N - 2.
 */
private fun countSubarrays(n: Int) = (n - 2 + 1) * (n - 2) / 2

Dry Run

nums = 
[1, 2, 3, 5, 7, 9]
 i