题目描述给你一个整数数组numsnumsnums返回numsnumsnums中最长等差子序列的长度。回想一下numsnumsnums的子序列是一个列表nums[i1],nums[i2],...,nums[ik]nums[i1], nums[i2], ..., nums[ik]nums[i1],nums[i2],...,nums[ik]且0i1i2...iknums.length−10 i1 i2 ... ik nums.length - 10i1i2...iknums.length−1。并且如果seq[i1]−seq[i](0iseq.length−1)seq[i1] - seq[i]( 0 i seq.length - 1)seq[i1]−seq[i](0iseq.length−1)的值都相同那么序列seqseqseq是等差的。示例 1输入nums [3,6,9,12]输出4解释整个数组是公差为 3 的等差数列。示例 2输入nums [9,4,7,2,10]输出3解释最长的等差子序列是 [4,7,10]。示例 3输入nums [20,1,15,3,10,5,8]输出4解释最长的等差子序列是 [20,15,10,5]。算法思想先根据经验 题目要求得到初步的状态表示经验就是以某个位置为结尾题目要求是最长等差子序列的长度所以dp[i]dp[i]dp[i]表示以iii为结尾的所有子序列中最长等差子序列的长度再根据这个状态表示推导一下状态转移方程要想得到dp[i]dp[i]dp[i]肯定要到[0,i−1][0, i-1][0,i−1]中找一个长度nums[j]nums[j]nums[j]让iii位置元素接在nums[j]nums[j]nums[j]之后。但是只知道nums[j],nums[i]nums[j], nums[i]nums[j],nums[i]的话无法确定nums[i]nums[i]nums[i]能否跟在nums[j]nums[j]nums[j]之后也就是根本不知道以jjj位置元素为结尾的最长等差子序列它的公差规模是什么样子的所以这个状态表示无法推出状态转移方程我们要换一个对于一个等差子序列如果知道它的末尾两个元素b,ab, ab,a那它的公差是a−ba - ba−b是可以推出前面所有元素的也就是.........2b−aba2b-aba2b−aba。所以状态表示应该是二维的dp[i][j]dp[i][j]dp[i][j]表示以iii位置元素和jjj位置元素为结尾的所有子序列中最长等差子序列的长度其中iji jij根据这个状态表示假设nums[i]bnums[j]anums[i] bnums[j] anums[i]bnums[j]a以这两个元素为结尾的等差序列它的倒数第三个数应该是2∗nums[j]−nums[i]c2 * nums[j] - nums[i] c2∗nums[j]−nums[i]c。假设nums[k]cnums[k] cnums[k]c根据ccc的情况推导状态转移方程ccc在numsnumsnums中存在并且kik iki时说明有以kkk位置和iii位置元素结尾的等差子序列后面跟上个aaa就是新的等差子序列此时dp[i][j]dp[k][i]1dp[i][j] dp[k][i] 1dp[i][j]dp[k][i]1ccc在numsnumsnums中存在但是ikji k jikj此时以iii位置元素和jjj位置元素为结尾的等差子序列只能是[nums[i],nums[j]][nums[i], nums[j]][nums[i],nums[j]]所以dp[i][j]2dp[i][j] 2dp[i][j]2ccc在numsnumsnums中不存在此时以iii位置元素和jjj位置元素为结尾的等差子序列只能是[nums[i],nums[j]][nums[i], nums[j]][nums[i],nums[j]]所以dp[i][j]2dp[i][j] 2dp[i][j]2如果就这么做题当填dp[i][j]dp[i][j]dp[i][j]时需要从后到前遍历[0,i−1][0, i-1][0,i−1]区间查找与nums[i]nums[i]nums[i]最近的nums[k]nums[k]nums[k]这是非常耗时的所以需要进行优化在填表时有两种方法固定等差子序列的倒数第一个数nums[j]nums[j]nums[j]枚举倒数第二个数nums[i]nums[i]nums[i]固定等差子序列的倒数第二个数nums[i]nums[i]nums[i]枚举倒数第一个数nums[j]nums[j]nums[j]在这里我们采用第二种填表方法使用一个哈希表记录元素和下标的映射关系然后在遍历numsnumsnums填表的时候当固定了一个nums[i]nums[i]nums[i]枚举完它后面的所有的nums[j]nums[j]nums[j]后将nums[i]nums[i]nums[i]记录到哈希表中iii向后进行移动。这样就可以在遍历numsnumsnums的过程中在哈希表中记录下离nums[i]nums[i]nums[i]最近的nums[k]nums[k]nums[k]了如果采用第一种方法iii的移动次数会达到O(n2)O(n^{2})O(n2)级别效率太低除开这些剩下的就是一些细节问题初始化将dpdpdp表的所有元素初始化为222因为规定了iji jij填表时i,ji, ji,j一定指向前后不同的值等差子序列长度至少为222返回值dpdpdp表的最大值代码classSolution{public:intlongestArithSeqLength(vectorintnums){intnnums.size();vectorvectorintdp(n,vectorint(n,2));unordered_mapint,inthash;// 元素 - 下标hash[nums[0]]0;intret2;for(inti1;in-1;i){for(intji1;jn;j){intc2*nums[i]-nums[j];if(hash.find(c)!hash.end()){intkhash[c];dp[i][j]dp[k][i]1;}retmax(ret,dp[i][j]);}hash[nums[i]]i;}returnret;}};
