LeetCode 1218. Longest Arithmetic Subsequence of Given Difference【哈希表,动态规划】中等

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.

A subsequence is a sequence that can be derived from arr by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].

Example 2:

Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.

Example 3:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

Constraints:

• 1 <= arr.length <= 10^5
• -10^4 <= arr[i], difference <= 10^4

题意：给定一个数组 arr 和一个公差 difference ，在数组 arr 中寻找公差为 difference 的最长等差子数列的长度。

解法 哈希表+动态规划

我们定义状态为：$dp[i]$ 为考虑前 $i$ 个数（第 $i$ 个数必选）时，得到的最长定差子序列长度。不失一般性考虑 $dp[i]$ 该如何转移，分情况讨论：

• $dp[i]$ 独立成为一个子序列，此时有 $dp[i]=1$ ；
• $arr[i]$ 接在某一个数的后面，由于给定了差值 $difference$ ，可直接算得上一位的值为 $prev=arr[i]-difference$ ，此时应找到为 $prev$ 的 $arr[j]$ 的最新位置（下标最大，同时满足 $j<i$ ），在此基础上加一即可，即有：$$dp[i]=dp[rec[prev]]+1$$

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {int n = arr.size(), ans = 0;int dp[n];unordered_map<int, int> rec;for (int i = 0; i < n; ++i) {dp[i] = 1;int prev = arr[i] - difference;if (rec.find(prev) != rec.end()) dp[i] = dp[rec[prev]] + 1;ans = max(ans, dp[i]);rec[arr[i]] = i;}return ans;}
};

解法2 （哈希表）值域形式的动态规划

解法1中使用 $dp[i]$ 记录以 $nums[i]$ 结尾的最长定差子序列长度，$rec[nums[i]]$ 则记录 $nums[i]$ 出现的下标。不妨将二者结合，设 $dp[nums[i]]$ 为以 $nums[i]$ 结尾的最长定差子序列长度，用哈希表作为 $dp$ ，简化代码书写：

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {int n = arr.size(), ans = 0;unordered_map<int, int> dp;for (int i = 0; i < n; ++i) {int prev = arr[i] - difference;dp[arr[i]] = dp[prev] + 1;ans = max(ans, dp[arr[i]]);}return ans;}
};