专栏 | 九章算法
网址 | www.jiuzhang.com
题目描述
给定一整数数列，问数列有多少个子序列是等差数列。
即对于包含N个数的数列A，A(0),A(1),……,A(N-1)，有多少组（P(0),P(1),……,P(k)）满足0<=P(0)<P(1)<……<P(k)<N，且A(P(0)),A(P(1)),……,A(P(k))为等差数列。
等差数列至少包含3个数，故必有k>=2，同时等差数列相邻两个数的差都是一样的，即A(P(1))-A(P(0) = A(P(2))-A(P(1)) = …… = A(P(k))-A(P(k-1)) = d，d被称为公差。
输入保证N个整数的取值范围均为-2^31 ~ 2^31-1，并且0<=N<=1000，同时保证输出小于2^31-1。
样例
输入: [2, 4, 6, 8, 10]
输出: 7
说明:所有等差子序列为:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
解题思路分析
a.N个数的数列的子序列共有2^N个，考虑到N的范围，直接枚举然后判断该子序列是否为等差数列是不可行的。
b. 事实上，确定一个等差数列只需要三个数，一个是等差数列的长度L，还有两个是等差数列的最后两个数（也可以是任意两个中间的下标确定的数）。
记最后一个为E1，最后第二个为E2，则得公差d=E1-E2，通过公差可以推出等差数列中其余的数。
一个以E2,E1,结尾的等差数列，在末尾加上一个数E1+d后仍然是等差数列。于是我们可以使用动态规划求解：令g(i,j)为以A(j),A(i)结尾的等差子序列的个数（j<i），（即形如（……,A(j),A(i)）的等差数列的个数），然后我们可以通过枚举倒数第三个数A(k)来统计g(i,j)。
对于形如（……,A(k),A(j)）的等差子序列来说，如果有A(i)-A(j)=A(j)-A(k)，那么对应的（……,A(k),A(j),A(i)）也为等差子序列，同时由于（A(k),A(j)）长度为2，不计入g(j,k)的中，但（A(k),A(j),A(i)）应计入g(i,j)中，故将g(j,k)计算入g(i,j)时还要额外加1。
于是我们有g(i,j)=Σ(g(j,k)+1)，其中k满足k<j且A(i)-A(j)=A(j)-A(k)。将所有得到的g(i,j)相加即可得到所有等差子序列的个数。这个算法的时间复杂度为O(N^3)，考虑到N的范围，这样的时间复杂度可以接受，而且与下面讲的算法相比简洁许多。
c. 时间复杂度为O(N^2)的动态规划（要用到HashMap）
Ⅰ. 我们令f(i,d)表示以A(i)结尾，公差为d的等差子序列的个数，这里我们允许存在长度为2的等差子序列（所以对于数列中任意两个数组成的子序列，我们都暂时认为其为等差子序列）。
那么对于一对(i,j)，j<i，A(i)-A(j)=d，对于所有以A(j)结尾，公差为d的等差子序列来说，后面再跟上A(i)之后还是公差为d的等差子序列，但变成了以A(i)结尾，再加上一对(A(j),A(i))，就得到了所有形如（……,A(j),A(i)）的等差子序列。
换言之，j将对f(i,d)贡献f(j,d)+1。故f(i,d)等于所有满足j<i且A(i)-A(j)=d的(f(j,d)+1)之和。
Ⅱ. 一个问题是d的范围其实很大（-2^32+1 ~ 2^32-1），如果要对所有可能的d进行枚举，那么在时间上和空间上都是受不了的。
虽然d的取值范围很大，但是对于N个数来说，两两之差最多只可能有N(N-1)/2种；而对于1个数A(i)来说，只需考虑所有小于i的j所产生的d=A(i)-A(j)，最多有i种可能。
所以，对于每一个i，可以用一个HashMap来存储键值对(d,f(i,d))。另一个问题是，我们在计算f(i,d)时，允许等差子序列长度为2（这一点是必要的，因为没有长度为2的序列的话，就没法在其末尾加上一个数得到更长的子序列），但答案要求的是所有长度至少为3的等差子序列的个数。
解决这个问题的方法有很多：在计算f(i,d)时，f(j,d)所表示的所有子序列长度都至少为2，在末尾加上A(i)之后，就成了满足条件的等差子序列，故可以在计算f(i,d)的同时累加所有f(j,d)，最后即可得到正确的答案（这种写法比较简洁但不太直观）；
也有一种比较容易理解的方法，那就是对所有f(i,d)之和，即所有长度至少为2的等差子序列的个数，减去长度为2的等差子序列的个数，而由于任意两个数都构成长为2的等差子序列，所以其个数为N(N-1)/2，两者相减得到的差即为正确答案。
Ⅲ. 总结一下这个动态规划算法：对于每个i=0,1,2,……,N-1，创建一个HashMap存储键值对(d,f(i,d))，f(i,d)的初值为0，枚举j<i，d=A(i)-A(j)，则f(i,d)增加f(j,d)+1，同时对答案增加f(j,d)。计算完所有的i之后即可得到答案。
一个小细节是，如果d不在[-2^31+1 , 2^31-1]的范围内，那么以这个d为公差的数列长度不可能是3或3以上，故对于d在这个范围外的情况可以直接跳过。
利用HashMap存取f(i,d),f(j,d)的复杂度为O(1)，i,j枚举的复杂度为O(N^2)，故总的时间复杂度为O(N^2)。
参考程序
面试官角度分析
这道题的解法为动态规划，但是需要注意许多细节，最优算法还需结合HashMap，总体难度中等偏上，正确给出O(N^3)算法可以hire，正确给出O(N^2)可以strong hire。
lintcode相关问题链接
推荐阅读：
- 《北美IT企业fulltime薪资大曝光》
- 《IT 简历模板大放送 | 《如何写好技术简历》讲座精华总结》
- 《offer收割机的求职秘诀 | <如何成为offer达人>讲座精华总结》
- 《Google offer 如何谈判？听听 Google recruiter 怎么说！》
- 《面试遇到做过的题怎么办？》
- 《冷冻期大揭秘 | Google、FB、Amazon、Linkedin冷冻期》
- 《面试前如何了解一家IT企业？试试官方技术博客！》
- 《北美IT企业intern薪资大曝光》
- 《16个behavior question 的面试官解析及tips》
- 《Google晋升机制 | 大公司如何升级打怪, 获得晋升？》
欢迎关注我的微信公众号：九章算法（ninechapter）。
精英程序员交流社区，定期发布面试题、面试技巧、求职信息等
