[LeetCode] 1218. Longest Arithmetic Subsequence of Given Difference

[grandyang]

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 <= 105
• -104 <= arr[i], difference <= 104

这道题让求给定差值的最长等差子序列，既然是子序列，就表示数字是不用连续的。对于这种数组玩极值的题目，很大的可能就是用动态规划 Dynamic Programming 来做，这道题也不例外。博主最开始想的方法比较简单粗暴，用一个一维的 DP 数组，其中 dp[i] 表示最后一个数字是 arr[i] 的等差子序列的长度，对于状态转移方程就是遍历每个 [0, i-1] 区间的j，若 dp[i] - dp[j] 等于 difference，则用 dp[j]+1 来更新 dp[i]，但是这种平方级时间复杂度的方法还是不幸超时了 Time Limit Exceeded，对于一道 Medium 的题目，卡的这么严是博主没有想到的。

那怎么办呢，还有什么更快的方法吗？有的，这里博主先卖个关子，首先来思考一下，为啥上面的解法会超时，因为每次都遍历 arr[i] 前面所有的数字，绝大部分的遍历操作都是无效的，因为差值不是给定的 difference。这里既然差值是确定的，直接通过 arr[i] - difference 就是前一个数字了，只需要快速知道这个数字是否存在，而且最好还能知道以这个数字结尾的等差子序列的长度。这样的话，用 HashMap 建立一个映射就比较方便了，于是乎 dp[i] 就表示以数字i结尾的等差子序列的长度，更新的时候也很方便，用 1 + dp[i-difference] 来更新 dp[i]，然后用 dp[i] 来更新结果 res 即可，参见代码如下：

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

Github 同步地址:

#1218

参考资料：

https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/

https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/discuss/398196/C%2B%2B-O(n)-DP-using-Hashmap

LeetCode All in One 题目讲解汇总(持续更新中...)