LeetCode 1218. 最长定差子序列

Categories:

题目描述
思路分析
1. 解法一：哈希表动态规划（推荐）
相似题目

题目描述

✅ 1218. 最长定差子序列

思路分析

解法一：哈希表动态规划（推荐）

核心思路：

设 dp[x] 表示以值 x 结尾、且相邻差为 difference 的最长子序列长度。

遍历数组元素 v，状态转移为 dp[v] = dp[v - difference] + 1。

用哈希表维护 dp，在线更新并记录最大值。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度。

空间复杂度：O(n)，哈希表存储状态。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        Map<Integer, Integer> dp = new HashMap<>();
        int ans = 0;
        for (int v : arr) {
            int prev = dp.getOrDefault(v - difference, 0);
            int cur = prev + 1;
            dp.put(v, cur);
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}

func longestSubsequence(arr []int, difference int) int {
    dp := make(map[int]int)
    ans := 0
    for _, v := range arr {
        cur := dp[v-difference] + 1
        dp[v] = cur
        if cur > ans {
            ans = cur
        }
    }
    return ans
}

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	动态规划
1027. 最长等差数列	中等	DP
376. 摆动序列	中等	状态转移
673. 最长递增子序列的个数	中等	DP
1218. 最长定差子序列	中等	哈希 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/38406455