题目大意：
最长定差子序列
给你一个整数数组 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1218
解题思路分析：
本题需要考虑利用动态规划来解题。循环数组中的没一个数字，如果想知道当前数字是否存在于等差子序列中，只要查看当前位置之前是否出现过当前数字减去difference的数值，如果不存在，那么当前数字能组成的等差序列长度为1（当前数字自身），如果存在则组成新的等差数列的长度为前数组成的长度加一。
举个例子，比如[1,3,2,3]，difference为1。
先从第0位的数字1开始，由于之前没出现过0（1-1），因此1能组成的子序列长度为1。循环到第1位数字3，同样之前没出现过2（3-1），因此3能组成的子序列长度为1。循环至第2位的数组2，因为之前出现过1（2-1），1组成的序列长度为1，因此2的长度更新为2（1+1）。最后循环到末尾的数字3，之前出现过数字2（3-1），2组成的长度为2，因此3的长度更新为3（2+1）。
看下完整实现代码：
public int longestSubsequence(int[] arr, int difference) {
// 记录该数字结尾组成的子序列长度
Map<Integer,Integer> map = new HashMap<>();
int res=0; // 返回结果
for(int n : arr){ // 循环数组
// 查看n-difference是否出现过，出现过的话前值加一
int count = map.getOrDefault(n-difference, 0)+1;
res = Math.max(res, count); // 更新最大长度
map.put(n, count); // 将当前数字组成的序列长度保存至map
}
return res;
}本题解法运行时间为43ms。
Runtime: 43 ms, faster than 88.54% of Java online submissions for Longest Arithmetic Subsequence of Given Difference.
Memory Usage: 54.5 MB, less than 100.00% of Java online submissions for Longest Arithmetic Subsequence of Given Difference.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1218-longest-arithmetic-subsequence-of-given-difference解题思路分析/