力扣刷题2023-04-20-1——题目：1218. 最长定差子序列

给你一个整数数组 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

穷举代码：时长太长

count_max = 1for i in range(len(arr)):count = 1pre = arr[i]for j in range(i + 1, len(arr)):if arr[j] - pre == difference:count = count + 1pre = arr[j]if pre + difference not in arr[j:len(arr)]:breakif count > count_max:count_max = count

 使用动态规划：

        首先，我们定义一个哈希表 dp，其中键为数组 arr 中的元素，值为以该元素为结尾的最长等差子序列的长度。然后，我们遍历数组 arr 中的每个元素，将其加入到 dp 中，并尝试向前寻找是否存在以该元素为结尾的最长等差子序列。如果找到了，我们就更新 dp 中该元素对应的值。

        具体来说，我们可以对于数组中的每个元素 arr[i]，在 dp 中查找是否存在键为 arr[i] - difference 的元素，如果存在，则说明 arr[i] 可以与这个元素构成等差子序列，更新 dp[arr[i]] 为 dp[arr[i] - difference] + 1。如果不存在，则说明 arr[i] 无法与之前的元素构成等差子序列，此时 dp[arr[i]] 的值仍然为 1，即只包含 arr[i] 一个元素的子序列。

        最终，我们遍历 dp 中的所有值，找出其中的最大值，即为所求的最长等差子序列的长度。

以下是具体的实现代码：

def longestSubsequence(arr, difference):dp = {}for num in arr:if num - difference in dp:dp[num] = dp[num - difference] + 1else:dp[num] = 1return max(dp.values())

        时间复杂度：O(n)，其中 n 是数组 arr 的长度。我们需要遍历数组 arr 中的每个元素，并在 dp 中进行查找和更新，时间复杂度均为 O(1)。

        空间复杂度：O(n)，其中 n 是数组 arr 的长度。我们需要使用哈希表 dp 存储每个元素对应的最长等差子序列的长度，空间复杂度为 O(n)。