Ricky.L的随笔
0%

LeetCode.413.等差数列划分（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.413.等差数列划分（中等）

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。

题解

子数组起始索引和结束索引各不相同，可以先按结束索引给子数组分类，分析统计相同结束索引下的等差数列子数组个数，最后累加所有不同结束索引的等差数列子数组个数。

先看以nums[i]结尾的数组中等差子数组个数，可以设其值为a[i]。

等差数列如何判断？

nums[i] - nums[i - 1] && nums[i - 1] == nums[i - 2]

如果已知a[i - 1]，如何得到a[i]？即如何递推？

分两种情况：

  1. nums[i]不能跟前面的元素形成等差数列，那么a[i] = 0
  2. nums[i]能跟前面的元素形成等差数列，这时候会新增几个等差数列子数组？
    1. 新增长度最短的等差数列：nums[i - 2]、nums[i - 1]、nums[i]
    2. 所有以nums[i - 1]结尾的子数组，末尾加上nums[i]，所形成的新数组。所有以nums[i - 1]结尾的子数组的个数为a[i - 1]。
    即a[i] = a[i - 1] + 1

空间优化

a[i]只跟上一个状态有关，所以可以不用数组记录每一个状态，用一个变量记录上一个状态即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    fun numberOfArithmeticSlices(nums: IntArray): Int {
        val n = nums.size
        if (n <= 2) return 0
        var sum = 0
        var pre = 0
        for (i in 2 until n) {
            val isCommonDiff = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]
            val cur = if (isCommonDiff) pre + 1 else 0
            sum += cur
            pre = cur
        }
        return sum
    }
}