题意:给一个长度1000内的整数数列,求有多少个等差的子数列。
如 【2,4,6,8,10】有7个等差子数列。
想了一个O(n^2logn)的DP算法 DP[i][j]为 对于原数列中的Ai到Ai为止 公差为j的数列的个数, 显然公差范围很大需要用到map(所以有了Logn)然而这道题用BST的map是要TLE或者MLE的
而HASH_MAP又无法使用,所以只好自己写一个hash了。
看了网上的一些解答 都是用的python 这道题用cpp还是有点麻烦。
关于动规方程 就不具体给出了 说一下思路
假设当前递推到了原数列的 Ai和Aj且Aj-Ai =dif
那么 以Ai为结尾且公差为dif的数列的情况我们是已经知道的,所以可以在O(n^2)的时间内求解。
下面给出cpp的代码
讲道理,调试Hash函数是坠痛苦的
int len2[1000][1500];
long long int num[1000][1500];
class Solution {
public:
int hash(int lo,long long x,long long num[][1500])
{
long long begin=x;
x=(x%1007+1007)%1007;
while(true)
{ if(num[lo][x]==0||num[lo][x]==begin){num[lo][x]=begin;return x;}
else x=(x+1);
}
}
int numberOfArithmeticSlices(vector<int>& A) {
int ans=0; memset(len2,0,sizeof(len2));
memset(num,0,sizeof(num));
int* lasp;
int *nowp;
for(int i=0;i<A.size();i++)
{ for(int j=i+1;j<A.size();j++)
{
long long int dif=(long long)A[j]-(long long)A[i];
int loci=hash(i,dif,num);
int locj=hash(j,dif,num);
lasp=&len2[i][loci];
int sum=*lasp;
nowp=&len2[j][locj];
*nowp+=sum+1;
ans+=sum;
}
} return ans;
}
};