区间动态规划例题：最长等差数列问题（固定差值版本） 题目描述 给定一个整数数组 nums，返回数组中最长的等差子序列的长度。这里的等差子序列要求差值固定为 d（d 可以是任意整数，包括 0 和负数）。子序列不要求连续，但必须保持原数组中的相对顺序。 例如： 输入：nums = [ 1, 5, 7, 8, 5, 3, 4, 2, 1 ], d = -2 输出：4 解释：最长的等差子序列是 [ 7, 5, 3, 1 ]，相邻元素差值都是 -2。 解题思路 这个问题可以用动态规划解决。我们定义 dp[ i] 表示以第 i 个元素结尾的、公差为 d 的最长等差数列的长度。关键是要快速找到前面满足 nums[ j] = nums[ i ] - d 的元素 j。 详细步骤 状态定义 定义 dp[ i] 为以 nums[ i ] 结尾的、公差为 d 的最长等差数列长度。 状态转移方程 对于每个位置 i，我们需要找到前面某个位置 j（j < i），使得 nums[ j] = nums[ i ] - d。如果存在这样的 j，那么： dp[ i] = dp[ j ] + 1 如果不存在这样的 j，那么 dp[ i ] = 1（只有当前元素自己） 寻找前驱元素的方法 为了快速找到满足 nums[ j] = nums[ i ] - d 的 j，我们可以使用哈希表记录每个数值最近出现的位置。但注意数组可能有重复元素，所以需要记录每个数值的所有出现位置，或者从后往前找最近的一个。 更实用的方法是：在遍历 i 的同时，用一个哈希表记录每个数值最后一次出现的位置。这样对于每个 i，我们计算 prev = nums[ i ] - d，如果 prev 在哈希表中存在，我们就找到了一个 j。 算法流程 初始化一个哈希表 last_ index，用于记录每个数值最近出现的下标 初始化 dp 数组，长度与 nums 相同，初始值都为 1 遍历 i 从 0 到 n-1： 计算 prev = nums[ i ] - d 如果 prev 在 last_ index 中存在，设 j = last_ index[ prev ] 那么 dp[ i] = dp[ j ] + 1 更新 last_ index[ nums[ i] ] = i 返回 dp 数组中的最大值 示例演示 以 nums = [ 1, 5, 7, 8, 5, 3, 4, 2, 1 ], d = -2 为例： i=0: nums[ 0]=1, prev=3, 不存在 → dp[ 0 ]=1 i=1: nums[ 1]=5, prev=7, 不存在 → dp[ 1 ]=1 i=2: nums[ 2]=7, prev=9, 不存在 → dp[ 2 ]=1 i=3: nums[ 3]=8, prev=10, 不存在 → dp[ 3 ]=1 i=4: nums[ 4]=5, prev=7, 存在(j=2) → dp[ 4]=dp[ 2 ]+1=2 i=5: nums[ 5]=3, prev=5, 存在(j=4) → dp[ 5]=dp[ 4 ]+1=3 i=6: nums[ 6]=4, prev=6, 不存在 → dp[ 6 ]=1 i=7: nums[ 7]=2, prev=4, 存在(j=6) → dp[ 7]=dp[ 6 ]+1=2 i=8: nums[ 8]=1, prev=3, 存在(j=5) → dp[ 8]=dp[ 5 ]+1=4 最大值为 4，与示例一致。 复杂度分析 时间复杂度：O(n)，只需要遍历数组一次 空间复杂度：O(n)，用于存储哈希表和 dp 数组 这种方法高效地解决了固定公差的等差数列问题，通过哈希表优化了前驱元素的查找过程。