【在線編程產品介紹】
阿里雲開發者社區在線編程：
免費刷題大神器，助你拿到好offer
周賽月賽不停歇，做題還能領獎品
大賽筆試全真題，常做常新有驚喜
點擊鏈接開始產品體驗：https://developer.aliyun.com/coding
本文為大家介紹的是“64.尋找等比數列”的解法探究。先來看一下題目內容：
題目詳情
查看題目：64.尋找等比數列 Alice和Bob都是數學高手，有一天Alice給了Bob一個長度為n的數組a，要求Bob在數組中找出3個數，要求三個數能夠組成一個公比為k的等比數列，且不改變三個數在數組a中的位置關係。
為了降低難度，Alice只要求Bob回答數組a中有多少個這樣的等比數列。
輸入一個整數n表示數組長度、公比k(1<=n,k<=2*10^5)和包含n個數的數組a(-10^9<=ai<=10^9)
輸出一個數字，表示數組a中包含Alice要求的等比數列的數量。
示例1
輸入：
5
2
[1,1,2,2,4]
輸出：
4
題解思路
方法1：逐個遍歷（超時）
最簡單的方法，就是遍歷數組中所有可能的三元組，逐個檢驗每組數是否符合公比為k的等比數列的性質。
對於較長的用例，這麼做顯然是超時的，不通過。
時間複雜度：O(n^3)
空間複雜度：O(1)
方法2：動態規劃
本題充分利用下面兩個隱藏規律，就可以使用動態規劃：
- “長度為3的等比數列”，滿足了動態規劃的最優子結構性質
數列中每個數字只有4種可能的狀態。其中帶*號的狀態可以同時存在，且靠後的狀態可以由前面的狀態轉換而來：
- 同時屬於一個或多個等比數列的第1項
- 同時屬於一個或多個等比數列的第2項
- 同時屬於一個或多個等比數列的第3項
- 無法與前後數字組成任何等比數列
- “不允許調換順序”，滿足動態規劃的子問題不重疊性和無後效性性質
表示數字處於上面哪種狀態，完全由這個數字及其之前的數字決定，它的狀態與它後面數字的情形無關。
這就意味著，一次遍歷，同時用map將每個遍歷的數字歸屬到前面4種狀態中的1個或多個裡。遍歷結束，輸出第3種狀態“同時屬於一個或多個等比數列的第3項”中含有的數字數，就完成了動態規劃的過程。
時間複雜度：O(n)
空間複雜度：O(kn)
看完之後是不是有了答題思路了呢，快來練練手吧：64.尋找等比數列
在線編程周賽、月賽火熱進行中，更有限時答題活動，定製衛衣、雙肩揹包、機械鍵盤等多重好禮等你來拿~每天都有好禮相送~點擊瞭解周賽詳情：在線編程3月份比賽正式開啟！機械鍵盤等你拿！
