算術スライスII-C++のサブシーケンス

N個の数が存在する配列Aがあるとします。その配列のサブシーケンススライスは、0 <=K0 =2です。したがって、算術スライスの数を返す必要があります。

したがって、入力が[2,4,6,8,10]の場合、7つの算術スライスがあるため、答えは7になります。 [2,4,6]、[2,4,10]、[4,6,8]、[6,8,10]、[2,4,6,8]、[4,6,8,10 ]、[2,4,6,8,10]、

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

• ret：=0
• あるマップdp別のマップcntを定義する
• Aから要素を取得して1つのセットを定義します
• n：=Aのサイズ
• iを初期化する場合：=1、i
• jを初期化する場合：=i-1、j> =0の場合、更新（jを1つ減らす）、実行-
  • diff：=A [i]-A [j]
  • diff <=-infまたはdiff>infの場合、-
    • 次の部分を無視し、次の反復にスキップします
  • temp：=dp [j、diff]diffがマップdp[j]にある場合、それ以外の場合は0
  • ret：=ret + temp
  • （A [i] + diff）がsに存在する場合、-
    • dp [i、diff]：=dp [i、diff] + temp + 1

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

例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int numberOfArithmeticSlices(vector<int>& A) {
      int ret = 0;
      unordered_map <lli, unordered_map <lli, lli> > dp, cnt;
      unordered_set <int> s (A.begin(), A.end());
      int n = A.size();
      for(int i = 1; i < n; i++){
         for(int j = i - 1; j >= 0; j--){
            lli diff = (lli)A[i] - (lli)A[j];
            if(diff <= INT_MIN || diff > INT_MAX) continue;
            int temp = dp[j].count(diff) ? dp[j][diff] : 0;
            ret += temp;
            if(s.count(A[i] + diff))dp[i][diff] += temp + 1;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {2,4,6,8,10};
   cout << (ob.numberOfArithmeticSlices(v));
}

入力

{2,4,6,8,10}

出力

7