算术切片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