413.等差数列划分

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

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

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

子数组 是数组中的一个连续序列。

本题首先需要根据等差数组的定义，求出每一大部分的等差数组，然后再对每一整个等差数组进行划分。首先对于求等差数组，只需要在有两个的基础上，看后续的差值是否和前两个一致。因此需要一直保持至少有两个起步判断是否构成等差数组。因此，当第i个元素的值无法与之前的值形成等差数组时，则将第i个，第i-1个作为新的一个等差数组的开始，并保存前一个等差数组的最大长度。之所以保存最大长度，是因为题目要求求解的是所有等差数组的个数，及上述中求出的等差数组中可能包含多个长度小一点的等差数组。而求法也很简单，长度为n的等差数组内一共有（n-1）*（n-2）/2个。（长度是n有1个，长度n-1有2个，长度n-2有3个。。。。。长度为3有1个，加起来一共（n-1）*（n-2）/2个）。

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n=nums.size();if(n<=2)return 0;// cout<<"   ---";vector<int>numbers(n,0);int gap=nums[1]-nums[0];numbers[0]=1,numbers[1]=2;//vector<int>ret(n,0);int k=0;for(int i=2;i<n;i++){int cur=nums[i];if(cur-nums[i-1]==gap){numbers[i]=numbers[i-1]+1;}else{   //  ret[k++]=numbers[i-1];numbers[i]=2;gap=nums[i]-nums[i-1];}}int ret=0;for(int i=1;i<n;i++){if(numbers[i]==2){ int l=numbers[i-1];ret+=((l-2)*(l-1)/2);}}int l=numbers.back();ret+=((l-2)*(l-1)/2);return ret;}
};