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