leetcode 413--等差数列片

图片.png

• 基本想法：
  等差数列片：意味着有不同的差值.
  例如：1 2 3 8 9 10：需要有两个部分

1. 完成等差：需要记住项数：一共有几个数据 1 2 3 一共有三个数据，项数是3，一共只有一种。下面就是等差数列公式推导：

   
   
   图片.png

n是数列项数，一共有(n-1)(n-2)0.5 个---也就是等差数列求和公式。

2. 累计一共有多少个等差数列

C++

int numberOfArithmeticSlices(vector<int>& A) {
        int cnt=2;
        int ans=0;
        for(int i=2;i<A.size();i++){
            if(A[i]-A[i-1]==A[i-1]-A[i-2])
                cnt++;
            else{
                if(cnt>2)
                    ans+=(cnt-2)*(cnt-1)*0.5;
                cnt=2;
            }
        }
        if(cnt>2)
            ans+=(cnt-2)*(cnt-1)*0.5;
        return ans;
    }

JAVA:

public int numberOfArithmeticSlices(int[] A) { 
        int cnt=2;
        int ans=0;
        for(int i=2;i<A.length;i++){
            if(A[i]-A[i-1]==A[i-1]-A[i-2])
                cnt++;
            else{
                if(cnt>2)
                    ans+=(cnt-2)*(cnt-1)*0.5;
                cnt=2;
            }
        }
        if(cnt>2)
            ans+=(cnt-2)*(cnt-1)*0.5;
        return ans;
    }