【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好offer
周赛月赛不停歇，做题还能领奖品
大赛笔试全真题，常做常新有惊喜
点击链接开始产品体验：https://developer.aliyun.com/coding
本文为大家介绍的是“64.寻找等比数列”的解法探究。先来看一下题目内容：
题目详情
等级：中等
知识点：DP
查看题目：寻找等比数列
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月份比赛正式开启！机械键盘等你拿！
