力扣题解（等差数列划分）

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;
    }
};

原文地址：https://blog.csdn.net/yyssas/article/details/140328355

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！