LeetCode 1218. Longest Arithmetic Subsequence of Given Difference

Problem

LeetCode 1218. Longest Arithmetic Subsequence of Given Difference

1. 题目简述

给出一个整形数组arr和一个整形数difference，找出arr所有子序列中以difference为间隔的最大长度。例如：

Examples：

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

2. 算法思路

Dynamic Programming

首先我们看一下给出的输入大小，基本上确定了不能使用暴力搜索，最多支持O(nlogn)级别的复杂度。所以我们判断使用动态规划来节约时间。

我们来看一下题目，要求找子序列，且difference确定，base case我们设定为长度为1的single element，maxLength就是1。然后对于第n个数，我们需要找到从第1个数到第 $ n - 1 $ 个数存不存在num[n] - difference，如果不存在，则说明以当前数字为结尾的最长子序列长度为1，也就是本身；如果存在，则为dp[n - difference] + 1，视情况更新maxLength。

对于判断是否存在num[n] - difference，有一个最好用的数据结构就是hashmap，key为数字，value为最后一次出现的index，对于重复的数，后出现的那个一定是包含先出现的情况。

dp[n] = dp[n - difference] + 1 (如果n - difference出现过)
dp[n] = 1 (如果n - difference没出现过)

3. 解法

Dynamic Programming bottom-up：数组最长为10^5，则dp数组长度为100001.

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int[] dp = new int[100000];
        // key是数值，value是last index
        Map<Integer, Integer> dict = new HashMap();
        int longest = 1;

        for (int i = 0; i < arr.length; i++) {
            int targetIndex = dict.getOrDefault(arr[i] - difference, -1);
            dict.put(arr[i], i);
            if (targetIndex == -1) {
                dp[i] = 1;
                continue;
            } else {
                dp[i] = dp[targetIndex] + 1;
                longest = Math.max(longest, dp[i]);
            }
        }

        return longest;
    }
}