1218最长定差子序列

题目：给你一个整数数组 arr 和一个整数 difference，请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列，并返回其中最长的等差子序列的长度。
链接：https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference

法一：自己的代码（超时和改进后的）

思路：基本的动态规划题，由于无后效性，即以arr[i]结尾的最长定差数列只与前面的数有关，对于查询的题目，一定要考虑时间复杂度，如果是n方很可能超时，这道题直接查询会超时，应该用字典的get方法来实现，所用的时间是常数级。用get方法的时候，如果该键不存在，返回默认值。

# if k in arr[:i]:这个每次都要找该值是否存在，最终的时间复杂度是n方
from typing import List
from collections import defaultdict
class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        memo = defaultdict(lambda :1)
        memo[arr[0]] = 1
        size = len(arr)
        res = 1
        for i in range(1, size):
            k = arr[i] - difference
            # 如果这个数在之前出现了，则将该等差数列的长度加1，最后返回最大值
            if k in arr[:i]:
                memo[arr[i]] = 1 + memo[k]
        return  (max( res, max(list(memo.values()))))

# 执行用时 :960 ms, 在所有 Python3 提交中击败了16.67% 的用户
# 内存消耗 :26.5 MB, 在所有 Python3 提交中击败了35.53%的用户
from typing import List
from collections import defaultdict
class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        size = len(arr)
        memo = defaultdict(lambda :size)
        cache = defaultdict(lambda :1)
        cache[arr[0]] = 1
        res = 1
        # key是数组中的元素，value是该值的最小索引
        for i,j in enumerate(arr):
            memo[j] = min(memo[j], i)
        for i in range(1, size):
            k = arr[i] - difference
            # 如果索引i前存在k，则将其加1
            if i > memo[k]:
                cache[arr[i]] = 1 + cache[k]
        # 最后返回最大值
        return  (max( res, max(list(cache.values()))))

# 别人的解法，主要是学会字典的get方法，get()方法返回键对应的值，
# get的第一个值是要寻找的键，第二个是默认的返回值，即如果该键不存在，则返回默认值
class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        d = {}
        for a in arr:
            d[a] = d.get(a - difference, 0) + 1
        return max(d.values())
if __name__ == '__main__':
    solution = Solution()
    # result = solution.longestSubsequence(arr = [1,5,7,8,5,3,4,2,1], difference = -2)
    # result = solution.longestSubsequence(arr = [1,3,5,7], difference = 1)
    result = solution.longestSubsequence(arr = [1,2,3,4], difference = 1)
    print(result)

ttt