leetcode 周赛 157 5214. 最长定差子序列 1218. Longest Arithmetic Subsequence of Given Difference

目录

1. 题解

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

题解

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        if len(arr) == 0: return 0
        mp = {}
        nt = [1 for i in range(len(arr))]
        i = len(arr) - 1
        while i >= 0:
            cur = arr[i]
            if cur + difference in mp:
                nt[i] = nt[mp[cur + difference]] + 1
            mp[cur] = i
            i -= 1
        i = 0
        ans = 1
        while i < len(arr):
            ans = max(ans, nt[i])
            i+=1
        return ans

从后往前遍历，记录出现的所有的数字的位置，这里可能会有重复的，直接覆盖掉就可以，因为这是一个贪心问题，我们可以只考虑最近的一个后续元素。nt[i] 记录的是从 arr[i] 开始的最长子序列的长度。