给你一个整数数组 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 <= 105-104 <= arr[i], difference <= 104
Related Topics
上代码
class Solution {
public int longestSubsequence(int[] arr, int difference) {
HashMap<Integer,Integer> map = new HashMap<>();
int[] dp = new int[arr.length];
dp[0]=1;
map.put(arr[0],1);
int i = 1;
for (; i < arr.length; i++) {
dp[i] = Math.max(dp[i-1], map.getOrDefault(arr[i]-difference,0)+1 );
map.put(arr[i],map.getOrDefault(arr[i]-difference,0)+1);
}
return dp[--i];
}
}思路简析
建立对应长度DP数组，第i位置表示最长等差子序列的长度，详细思路的写在注解里
class Solution {
public int longestSubsequence(int[] arr, int difference) {
HashMap<Integer,Integer> map = new HashMap<>();
int[] dp = new int[arr.length];
//第一位的时候显然最长一定为1
dp[0]=1;
//表示以arr[0]为结尾的等差数列子序列的长度为1
map.put(arr[0],1);
int i = 1;
for (; i < arr.length; i++) {
//第i位的时候。
//此时也许当前值减去difference的值，在map中有记录存在有这个值结尾的等差数列，
//也可能这个等差数列的长度比之前[i-1]位的等差数列的长度要小，
//俩着取较大的一个
dp[i] = Math.max(dp[i-1], map.getOrDefault(arr[i]-difference,0)+1 );
//在map中记录或者更新更新以当前值结尾的等差数列子序列的最大长度
map.put(arr[i],map.getOrDefault(arr[i]-difference,0)+1);
}
return dp[--i];
}
}换个角度
上面的写法中使用HashMap的原因是key值可能为负数，如果是正数int型的key的话一般还有一种做法是直接用int[]数组代替hashmap来处理相关逻辑，比封装后的HashMap更加简洁高效，当时相对的也有更多局限性。
本题中给出了-10⁴ <= arr[i], difference <= 10⁴
那么arr[i]的范围就在-9999到9999之间，如果再加上需要和difference运算的话，那么应该是-20000 < arr[i] +/- difference < 20000 之间，那么对应的上面的int[]数组代替hashmap的更加高效的选择的作法的话，就变成如下的代码
class Solution {
public int longestSubsequence(int[] arr, int difference) {
int[] map = new int[40001];
int[] dp = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
arr[i] = arr[i]+20000;
}
dp[0]=1;
map[arr[0]] = 1;
int i = 1;
for (; i < arr.length; i++) {
dp[i] = Math.max(dp[i-1], map[arr[i]-difference]+1 );
map[arr[i]]= map[arr[i]-difference]+1;
}
return dp[--i];
}
}
