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