1218. 最长定差子序列

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/
Star
给你一个整数数组 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
通过次数36,722提交次数71,424

法1 hashMap 动态规划

思路
动态规划 题型2， 单序列加强版。
但本题目会超时，需要hahsMap辅助。具体思路如下：
因为每次都是查找之前小于当前元素固定的差值的元素。所以用hashMap来作为dp数组，查找的时候为O(1)查找。
题解
class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        if len(arr) == 1:
            return 1

        dp = collections.defaultdict(int)
        dp[arr[0]] = 1
        for num in arr[1:]:
            dp[num] = dp[num-difference] + 1
        
        return max(dp.values())