难度: Medium
如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。
示例 1：
输入：nums = [1,2,3,4] 输出：3 解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2：
输入：nums = [1] 输出：0
提示：
1 <= nums.length <= 5000-1000 <= nums[i] <= 1000运行时间: 24 ms
内存: 16.3 MB
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
for i in range(2, n):
if nums[i - 1] * 2 == nums[i] + nums[i - 2]:
dp[i] = dp[i - 1] + 1
return sum(dp)
这个题解使用动态规划来解决问题。定义状态 dp[i] 表示以 nums[i] 结尾的等差数列的个数。当 nums[i-1] * 2 == nums[i] + nums[i-2] 时，说明 nums[i-2], nums[i-1], nums[i] 构成等差数列，此时 dp[i] = dp[i-1] + 1，即在前一个状态的基础上再加上 nums[i]。最后对 dp 数组求和即可得到所有的等差数列个数。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n # 定义状态数组 dp，dp[i] 表示以 nums[i] 结尾的等差数列的个数
for i in range(2, n): # 从下标 2 开始遍历数组
if nums[i - 1] * 2 == nums[i] + nums[i - 2]: # 判断是否构成等差数列
dp[i] = dp[i - 1] + 1 # 状态转移方程
return sum(dp) # 返回 dp 数组的和，即所有的等差数列个数
在这个动态规划问题中，dp[i] 表示以 nums[i] 结尾的等差数列片段的数量。这个定义帮助我们只关注以当前元素结尾的等差数列情况，而不需要从头到尾重新考虑所有可能的等差数列。通过分解问题为小规模的子问题，我们可以通过前一个状态（dp[i-1]）来推导出当前状态（dp[i]），这样可以有效地利用之前的计算结果，避免重复工作。
状态转移方程 dp[i] = dp[i-1] + 1 是基于等差数列的性质得来的。当 nums[i-2], nums[i-1], nums[i] 构成一个等差数列时，以 nums[i-1] 结尾的等差数列片段可以通过添加 nums[i] 来扩展，形成一个新的等差数列片段。因此，新的等差数列片段的数量至少是 dp[i-1] 加上新形成的片段。这里 '+1' 表示的就是新增的由这三个数字构成的等差数列片段。
这种方法从下标2开始遍历数组是因为构成等差数列至少需要3个数字。若从下标0或1开始，我们无法检查前两个元素是否形成等差数列，因为等差数列的定义至少涉及到三个数。因此，从下标2开始是为了确保每次检查时，都有足够的元素来判断是否形成等差数列。
这个条件是基于等差数列的定义来的，即序列中任何连续的三个数，第二个数是第一个数和第三个数的算术平均。当 nums[i-1] * 2 == nums[i] + nums[i-2] 成立时，意味着 nums[i-1] 等于 nums[i-2] 和 nums[i] 的平均值，这保证了 nums[i-2], nums[i-1], 和 nums[i] 形成等差数列。因此，这个条件是检验和确认子数组是否为等差数列的一个正确和有效的方法。