0413-等差数列划分 #

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

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

例如，[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 处等差数列的个数
后续 dp[i] 如果 nums[i] - nums[i-1] = nums[i-1] - nums[i-2], 则 dp[i]+=1 否则 dp[i]=0

排列组合

我们从3个数字开始 123 1 个
1234 3 个(123,234,1234)
12345 6 个(123,234,345,1234,2345,12345)
123456 10 个(123,234,345,456,1234,2345,3456,12345,23456,123456)
我们发现 1,3,6,10 他们都减去前面的数就是 1,2,3,4其实就是在前面的基础上累加
所以，只要数组连续 add+=1 然后 ans+=add，当不连续的时候 add 重新设置为 0

官方解释： 差分+计数 https://leetcode.cn/problems/arithmetic-slices/solution/deng-chai-shu-lie-hua-fen-by-leetcode-so-g7os/

参考代码 #

public class Solution {
    public int NumberOfArithmeticSlices(int[] nums) {
    	if(nums.Length <=2){
    		return 0;
    	}
    	int ans = 0;
    	int add = 0;
    	for(int i=2; i<nums.Length; i++){
    		if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2]){
    			add+=1;
    			ans+=add;
    		}
    		else{
    			add=0;
    		}
    	}
    	return ans;
    }
}