九章演算法 | Facebook 面試題：等差子序列
撰文 | JZ
專欄 | 九章演算法
問題描述
給定一整數數列，問數列有多少個子序列是等差數列。
即對於包含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)。
參考程序
九章演算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時在線授課為你傳授面試技巧
面試官角度分析
這道題的解法為動態規劃，但是需要注意許多細節，最優演算法還需結合HashMap，總體難度中等偏上，正確給出O(N^3)演算法可以hire，正確給出O(N^2)可以strong hire。
lintcode相關問題鏈接
最長上升子序列
推薦閱讀：