C++の算術スライス

少なくとも3つの要素で構成され、2つの連続する要素の差が同じである場合、数のシーケンスが算術と呼ばれるとします。したがって、たとえば、これらは等差数列です：[1、3、5、7、9]、[7、7、7、7]、[3、-1、-5、-9]、しかし次のシーケンスはそうではありません算術。 [1、1、2、5、7]

ここで、N個の数値で構成されるゼロインデックス配列Aが与えられます。その与えられた配列のスライスは、0 <=P

したがって、入力が[1,2,3,4]の場合、要素は[1,2,3]、[2,3,4]、および[1,2,3、 4]

これを解決するには、次の手順に従います-

• ret：=0、n：=Aのサイズ、サイズnの配列dpを作成
• 2からn–1の範囲のiの場合
  • a [i] – a [i – 1] =a [i – 1] – a [i – 2]の場合、
    • dp [i]：=1 + dp [i-1]
    • retをdp[i]で増やします
• return ret

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
      int numberOfArithmeticSlices(vector<int>& A) {
         int ret = 0;
         int n = A.size();
         vector <int> dp(n);
         for(int i = 2; i < n; i++){
            if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]){
               dp[i] = 1 + dp[i - 1];
               ret += dp[i];
            }
         }
         return ret;
      }  
};
main(){
   vector<int> v = {1,2,3,4};
   Solution ob;
   cout << (ob.numberOfArithmeticSlices(v));
}

入力

[1,2,3,4]

出力

3