问题描述
给你一个整数数组 arr
和一个整数 difference
,请你找出并返回 arr
中最长等差子序列的长度,该子序列中相邻元素之间的差等于 difference
。
子序列 是指在不改变其余元素顺序的情况下,通过删除一些元素或不删除任何元素而从 arr
派生出来的序列。
示例 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⁵
-10⁴ <= arr[i], difference <= 10⁴
解题思路
利用哈希表,记录数组中每个元素,作为子序列末尾元素时,该元素对应的最长子序列的长度,有
if (ump.find(num - difference) != ump.end()) {
ump[num] = ump[num - difference] + 1;
} else {
ump[num] = 1;
}
代码
class Solution {
public:
int longestSubsequence(vector<int> &arr, int difference) {
unordered_map<int, int> ump;
for (auto &num : arr) {
if (ump.find(num - difference) != ump.end()) {
ump[num] = ump[num - difference] + 1;
} else {
ump[num] = 1;
}
}
int res = 0;
for (auto &num : ump) {
res = res < num.second ? num.second : res;
}
return res;
}
};
标签:arr,ump,1218,序列,num,差子,difference
From: https://www.cnblogs.com/zwyyy456/p/17478090.html