LeetCode 413. 等差数列划分*

具体思想:

双指针可以做,而且还挺快;

但是官方想用的方法是差分数组,这个属实是没想到,给忘了;

这里有一个小技巧;

自己计数是算最大距离阶乘的,但是其实可以不用这样算;

直接新开计数,3位+1,4位+2,。。。以此类推;

变相计算了阶乘;

具体代码:

双指针:

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        if(nums.size()<3){
            return 0;
        }
        int l=0,r=2;
        int div=nums[1]-nums[0];
        int cnt=0;
        while(r<nums.size()){
            if(nums[r]-nums[r-1]!=div){
                if(r-l>=3){
                    cnt+=cal(r-l-3+1);
                }
                l=r-1;
                if(r+1>nums.size())
                    return cnt;
                div=nums[l+1]-nums[l];
                r+=1;
                continue;
            }
            r++;
            if(r==nums.size()){
                if(r-l>=3){
                    cnt+=cal(r-l-3+1);
                }
            }
        }
        return cnt;
    }
    int cal(int n){
        int ret=0;
        while(n!=0){
            ret+=n;
            n--;
        }
        return ret;
    }
};

差分数组:

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        if(nums.size()<3)
            return 0;
        int d=nums[1]-nums[0];
        int ret=0;
        int t=0;
        for(int i=2;i<nums.size();i++){
            if(nums[i]-nums[i-1]==d){
                t++;
            }else{
                t=0;
                d=nums[i]-nums[i-1];
            }
            ret+=t;
        }
        return ret;
    }
};

版权声明:本文为m0_66776925原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。