难度: Medium
给你一个整数数组 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运行时间: 80 ms
内存: 27.0 MB
class Solution:
def longestSubsequence(self, arr: List[int], d: int) -> int:
# 用哈希表记录上一个能和当前元素拼接的元素（以其为结尾的长度）
# 因为差值固定，所以只需要查询一次信息，查询[值域的信息]
# 但往这个思路走 如果查询范围值域 就有了值域dp 树装数组 线段树等多种优化 信息的保存和传递就变得复杂
# arr.sort(reverse=d<0) 不能排序，示例要求固定位置
visited = defaultdict(int)
for x in arr:
visited[x] = visited[x-d] + 1
return max(visited.values())
此题解采用哈希表的方式解决问题，其核心思路在于利用一个哈希表（字典）来存储每个元素作为等差子序列末尾时的最长子序列长度。对于数组中的每个元素x，我们检查x - difference是否已经存在于哈希表中，如果存在，则x元素能够接在该等差子序列后，因此x作为末尾的最长子序列长度就是x - difference作为末尾的最长子序列长度加1。如果x - difference不存在于哈希表中，说明x作为子序列的起点，其长度为1。最后，通过遍历整个哈希表，返回其中的最大值，即为最长等差子序列的长度。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def longestSubsequence(self, arr: List[int], d: int) -> int:
# 创建一个字典来存储每个数字作为子序列末尾的最长长度
visited = defaultdict(int)
# 遍历数组中的每个元素
for x in arr:
# 更新当前数字x作为子序列末尾的最长长度，如果x-d在字典中，则在其基础上加1
visited[x] = visited[x-d] + 1
# 返回字典中的最大值，即为最长等差子序列的长度
return max(visited.values())
哈希表（字典）在此算法中被用于存储每个元素作为等差子序列末尾时的最大长度，主要是因为哈希表提供了快速的查找、插入和更新操作。通过使用哈希表，我们可以在O(1)的平均时间复杂度内查找任何元素是否已存在，以及其对应的子序列长度。这使得算法能够高效地更新序列长度，尤其是在处理大数据集时，能够显著提高性能。此外，哈希表的灵活性允许我们在遍历数组的同时动态地更新状态，避免了额外的空间和时间开销。
该算法可以适应数组中的重复元素。在处理重复元素时，算法会分别计算每个元素作为子序列末尾时的最大长度。即使是重复的值，每个实例都会被独立地考虑其能够延续的子序列长度。因此，重复的元素不会影响子序列长度的正确计算，它们将根据各自的位置和之前的元素来确定能否形成更长的子序列。
该算法假设`difference`可以是任何整数值（正数、负数或零），并且没有对其进行特殊处理。当`difference`为零时，算法会查找数组中与当前元素相同的连续元素来形成子序列。当`difference`为正或负时，算法逻辑寻找与当前元素差为`difference`的元素。这种设计使算法具有通用性并能处理各种情况。然而，这也意味着算法会依赖于输入满足一定的逻辑关系（如等差序列的定义），若输入不符合预期，算法不会进行额外的错误检查或处理。
原始算法是为整数数组设计的，因此在处理含有非整数元素（如字符串或浮点数）的数组时需要调整。对于浮点数，可以在保持算法逻辑不变的情况下直接应用，但需确保浮点精度问题不会导致计算错误。对于字符串或其他非数字类型，算法需要根据具体需求重写，例如通过定义字符串的差异操作或转换成可操作的数值格式。此外，还需要调整哈希表的键类型或增加类型检查以确保类型安全和操作的准确性。