算术切片II-C ++中的子序列

假设我们有一个数组A，其中存在N个数字。该数组的子序列切片是任意整数序列，例如（K0，K1，K2，…Kn），这样0 <= K0 <K1 <K2 <…<Kn <N。如果序列A [K0]，A [K1]，…A [Kn]是算术的，则A的Kn）称为算术切片，因此这意味着n> =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中的元素来定义一个

• n：= A的大小

• 对于初始化i：= 1，当i <n时，更新（将i增加1），-

• 差异：= A [i]-A [j]

• 如果diff <= -inf或diff> inf，则-

• temp：= dp [j，diff]当diff在映射dp [j]中时，否则为0

• ret：= ret +温度

• 如果（A [i] + diff）以s表示，则-

• 忽略以下部分，跳至下一个迭代

• dp [i，diff]：= dp [i，diff] + temp + 1

• 对于初始化j：= i-1，当j> = 0时，更新（将j减1），-

• 返回ret

让我们看下面的实现以更好地理解-

示例

#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