413. 等差數列劃分

如果一個數列 至少有三個元素 ，并且任意兩個相鄰元素之差相同，則稱該數列為等差數列。

例如，[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

解題思路

數組含義：dp[i]代表包含下標i的等差數組的個數

狀態轉移：如果nums[i]-nums[i-1]==nums[i-1]-nums[i-2],說明當前的nums[i]可以加入到以nums[i-1]結尾的任意數組當中，所以我們dp[i]=dp[i-1]+1,因為我們多增加了一個更長的等差數組

代碼

class Solution {public int numberOfArithmeticSlices(int[] nums) {int n=nums.length,res=0;int[] dp = new int[n];for(int i=2;i<n;i++){if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){dp[i]=dp[i-1]+1;res+=dp[i];}}return res;}
}