首先我们会想，如何能够确定一个等差数列．知道了首项，公差，就能往后推序列的其他元素．所以本题容易想到的一个思路就是正向地搜索．这样的话，光遍历首项和公差就是o(N^2)的复杂度，后续的DFS更是计算量巨大．
搜索不成的话，DP是个很常规的替代方案．考虑到本题是求方案的数量，所以DP解法的嫌疑就更大了．最常见的DP套路，就是考察待求的状态量DP[i]与之前的状态量DP[j]之间的推导关系，这里的DP[i]不妨就设计为题意要求的以元素j结尾的的等差数列的个数．
如果i是等差数列的最后一个，那么它之前的一个元素是什么呢？那么j=0~i-1都是有可能的，只要元素j是某个相同公差的等差数列的结尾元素．如果是的话，显然DP[i]+=DP[j]．由此，我们看到一个重要的因素，那就是公差diff．也就是说，判断j是否和i构成等差数列的条件，就是先计算diff=A[j]-A[i]，然后再考察j是否为一个公差为diff的等差数列的尾项．于是我们还需要在DP数组中给Ａ的每个元素开辟一个Hash，用来存储它所涉及的公差．
我们令dp[i][diff]表示以元素i结尾、公差为diff的等差数列（长度>=2）有多少个。为什么我们会这么定义“长度>=2”？假设我们后面能接上一个元素k并保持这个公差diff的话，对于k而言，以其为结尾的长度>=3的等差数列那就是dp[i][diff]，恰好就是我们想统计的。可见这样定义dp[i][diff]能给我们带来极大的方便。
当然，对于k而言，你也必须正确地更新dp[k][diff]。注意DP变量的定义，以k为结尾的长度>=2的等差数列应该有dp[i][diff]+1个，这“+1”就是代表着仅包含{i,k}两个元素的数列。
核心代码如下：
unorderd_map<int,int>DP[1000];
int count = 0;
for (int i=0; i<N; i++)
for (int j=0; j<i; j++)
{
diff = A[i]-A[j];
count += dp[j][diff]; // 构建了以j,i为倒数两位，且公差为diff的新等差数列(保证长度>=3)
if (dp[j].find(diff)==dp[j].end())
dp[i][diff] = 1;
else
dp[i][diff] += dp[j][diff]+1; // 更新以i为结尾，且公差为diff的等差数列(长度>=2)的个数。
}
return count; 这个思想和1027.Longest-Arithmetic-Sequence的解法一致，时间复杂度是o(N^2).
一个等差数列,可以通过后两位元素就能唯一确定.所以另一个很常见的DP解法,就是定义状态变量DP[i][j]表示为以元素i,j结尾的等差数列的个数.
我们通过i,j,查找之前是否存在一个索引k使得A[i]*2=A[k]+A[j].如果找到的话那就说明DP[i][j]+=DP[k][i]+1。其中DP[k][i]+1的意思是：以i,j为结尾的等差数列，大部分可以由以k,i为结尾的等差数列延长而来（多加上一个A[i]而已），但还多出来的一个就是仅含有k,i,j三个元素的等差数列。另外，这里为什么是+=而不是=，那是因为这样的k可能会有好几个(对应相同的A[k]值).
想通过A[k]值找到k,需要提前处理,用到一个一对应多的hash表unordered_map<int,vector>Map. 注意这种解法的时间复杂度是o(N^3).