给你一个整数数组 arr 和一个整数 difference,请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列,并返回其中最长的等差子序列的长度。
示例 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]。
提示:
1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
类似题目:
class Solution { //C++
public:
int longestSubsequence(vector<int>& arr, int difference) {
unordered_map<int,int> m;//等差数列结尾的数,最大长度
int maxlen = 1;
for(int i = 0, prev; i < arr.size(); ++i)
{
prev = arr[i]-difference;
if(m.count(prev))//前面有一个数与我构成等差数列
m[arr[i]] = m[prev] + 1;
else
m[arr[i]] = 1;
maxlen = max(maxlen, m[arr[i]]);
}
return maxlen;
}
};
412 ms 53.2 MB
class Solution:# py3
def longestSubsequence(self, arr: List[int], difference: int) -> int:
d = {}
maxlen = 1
for i in range(len(arr)):
if arr[i]-difference in d:
d[arr[i]] = d[arr[i]-difference] + 1
else:
d[arr[i]] = 1
maxlen = max(maxlen, d[arr[i]])
return maxlen
872 ms 27.3 MB