最长等差数列问题（任意差值版本） 题目描述 给定一个整数数组nums，返回数组中作为等差数列的最长子序列的长度。等差数列是指序列中相邻元素的差值相同的序列。子序列是通过删除原数组中的某些元素（也可以不删除）得到的序列，不改变剩余元素的相对顺序。 例如： 输入：nums = [ 3,6,9,12 ] 输出：4 解释：整个数组就是公差为3的等差数列。 输入：nums = [ 9,4,7,2,10 ] 输出：3 解释：最长的等差数列是[ 4,7,10]（公差为3）或[ 9,7,5]（但5不在数组中，实际是[ 4,7,10 ]）。 解题过程 这个问题要求找到最长的等差数列子序列（不要求连续）。由于差值可以是任意整数（正、负或零），我们需要一个能够处理各种差值的动态规划方法。 步骤1：定义状态 我们定义dp[ i][ d ]表示以第i个元素结尾，公差为d的等差数列的最大长度。但这里有个问题：d可能是任意整数，范围可能很大，不适合直接作为数组下标。 解决方案：使用哈希表来存储公差信息。我们可以定义： dp[ i]是一个哈希表，其中键是公差d，值是以nums[ i ]结尾、公差为d的等差数列长度。 步骤2：状态转移方程 对于每个位置i（0 ≤ i < n），我们需要考虑所有可能的j（0 ≤ j < i）： 计算差值d = nums[ i] - nums[ j ] 如果dp[ j]中存在公差d，那么dp[ i][ d] = dp[ j][ d ] + 1 否则，dp[ i][ d] = 2（因为至少nums[ j]和nums[ i ]可以构成等差数列） 同时，我们需要记录全局最大值max_ len。 步骤3：初始化 对于每个位置i，dp[ i ]初始化为空哈希表 最小等差数列长度至少为1（单个元素） 全局最大值max_ len初始化为1 步骤4：遍历顺序 外层循环：i从0到n-1 内层循环：j从0到i-1 步骤5：示例演示 以nums = [ 3,6,9,12 ]为例： i=0: dp[ 0 ] = {}（单个元素） i=1: j=0: d=6-3=3, dp[ 1][ 3 ] = 2 max_ len = max(1,2) = 2 i=2: j=0: d=9-3=6, dp[ 2][ 6 ] = 2 j=1: d=9-6=3, dp[ 2][ 3] = dp[ 1][ 3 ] + 1 = 3 max_ len = max(2,3) = 3 i=3: j=0: d=12-3=9, dp[ 3][ 9 ] = 2 j=1: d=12-6=6, dp[ 3][ 6 ] = 2 j=2: d=12-9=3, dp[ 3][ 3] = dp[ 2][ 3 ] + 1 = 4 max_ len = max(3,4) = 4 步骤6：复杂度分析 时间复杂度：O(n²)，需要两重循环 空间复杂度：O(n²)，最坏情况下每个位置可能存储O(n)个不同的公差 步骤7：边界情况处理 数组长度为0或1时直接返回长度 所有元素相同的情况（公差为0） 数组严格递增或递减的情况 步骤8：代码实现要点 使用字典列表或二维字典来存储dp值，注意处理哈希表的查找和更新操作。 这种方法的优势在于能够处理任意大小的公差，不受数值范围限制，适用于各种输入情况。