假设我们有一个数组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