1218. 最长定差子序列

题目描述给你一个整数数组arrarrarr和一个整数differencedifferencedifference请你找出并返回arrarrarr中最长等差子序列的长度该子序列中相邻元素之间的差等于differencedifferencedifference。子序列 是指在不改变其余元素顺序的情况下通过删除一些元素或不删除任何元素而从arrarrarr派生出来的序列。示例 1输入arr [1,2,3,4], difference 1输出4解释最长的等差子序列是 [1,2,3,4]。示例 2输入arr [1,3,5,7], difference 1输出1解释最长的等差子序列是任意单个元素。示例 3输入arr [1,5,7,8,5,3,4,2,1], difference -2输出4解释最长的等差子序列是 [7,5,3,1]。算法原理子序列问题可用动态规划解决状态表示dp[i]dp[i]dp[i]表示以iii为结尾的所有等差子序列中最长等差子序列的长度状态转移方程由于题目给定了差值differencedifferencedifference所以在知道arr[i]aarr[i] aarr[i]a的情况下可以推出它前面的那个值等于a−differenceba - difference ba−differenceb。因此当获得值aaa时就去arrarrarr的[0,i−1][0, i-1][0,i−1]区间中找一个值bbb根据bbb的情况有两种状态[0,i−1][0, i-1][0,i−1]区间中不存在bbb此时aaa自己为一个等差子序列dp[i]1dp[i] 1dp[i]1[0,i−1][0, i-1][0,i−1]区间中存在bbb此时aaa要跟在以bbb为结尾的等差子序列之后假设0ji−10 j i-10ji−1以bbb为结尾的等差子序列它的长度为dp[j]dp[j]dp[j]以aaa为结尾的等差子序列它的长度就是dp[j]1dp[j] 1dp[j]1但是如果这样做就要去遍历[0,i−1][0, i-1][0,i−1]区间了效率太低我们进行优化由于差值固定为differencedifferencedifference当得到arr[i]aarr[i] aarr[i]a时在[0,i−1][0, i-1][0,i−1]区间内找任意一个bbb均可得到以aaa为结尾的最长等差子序列长度所以使用一个哈希表hashhashhash保存某等差子序列最后一个值和该等差子序列长度的映射关系当得到aaa时在hashhashhash中查找bbbbbb不存在就保存hash[a]1hash[a] 1hash[a]1。bbb存在就保存hash[a]hash[b]1hash[a] hash[b] 1hash[a]hash[b]1并更新结果初始化刚开始哈希表什么都没有i0i 0i0时会得到aarr[0]a arr[0]aarr[0]在哈希表中查找[0,−1][0, -1][0,−1]区间上的值bbb肯定是找不到的此时会填入arr[0]0arr[0] 0arr[0]0所以哈希表不需要初始化填表顺序从左到右遍历arrarrarr填充哈希表返回值哈希表中的最大值代码classSolution{public:intlongestSubsequence(vectorintarr,intdifference){unordered_mapint,inthash;// 某等差子序列最后一个值 - 该等差子序列的长度intans1;for(inti0;iarr.size();i){intaarr[i];intba-difference;if(hash.find(b)!hash.end())// 之前有以 b 为结尾的子序列{intlenhash[b];hash[a]len1;// 在以 b 为结尾的子序列之后带上 aansmax(ans,len1);}else// 之前没有以 b 为结尾的子序列{hash[a]1;}}returnans;}};