最长等差数列 题目描述 给定一个整数数组 nums，返回数组中最长等差数列的子序列长度。等差数列是指数组中任意相邻两个元素的差值相等的序列。注意，子序列不要求连续，但需要保持原始顺序。 例如： 输入：nums = [ 3,6,9,12 ] 输出：4 解释：整个数组就是公差为3的等差数列。 输入：nums = [ 9,4,7,2,10 ] 输出：3 解释：最长的等差数列是 [ 4,7,10] 或者 [ 9,7,5 ]，长度都是3。 解题过程 这个问题要求我们找出最长的等差数列子序列。由于是子序列问题（不要求连续），我们可以使用动态规划来解决。 步骤1：理解问题关键点 等差数列由两个关键参数决定：公差d和序列 对于任意两个位置i和j（i<j），nums[ j]-nums[ i ]就是它们之间的公差 我们需要找到最长的序列，使得任意相邻元素差值相等 步骤2：定义状态 我们可以定义dp[ i][ d ]表示以第i个元素结尾，公差为d的等差数列长度。但是公差d可能是任意整数，甚至负数，所以我们需要另一种表示方法。 更常用的状态定义是： dp[ i][ j]表示以nums[ i]和nums[ j]作为最后两个元素的等差数列的最大长度（其中i <j） 步骤3：状态转移方程 对于任意位置j，我们遍历所有i <j： 计算公差d = nums[ j] - nums[ i ] 我们需要找到在i之前的一个位置k，使得nums[ i] - nums[ k ] = d 如果存在这样的k，那么dp[ i][ j] = dp[ k][ i ] + 1 如果不存在这样的k，那么dp[ i][ j] = 2（只有nums[ i]和nums[ j ]两个元素） 步骤4：具体实现细节 我们可以使用哈希表来优化查找过程： 对于每个位置i，我们维护一个哈希表，记录以i结尾的各个公差对应的最大长度 当我们处理位置j时，对于每个i<j，计算d = nums[ j]-nums[ i ] 在i的哈希表中查找公差d对应的长度，如果存在则dp[ i][ j ] = 该长度 + 1 更新j的哈希表 步骤5：算法步骤 如果数组长度≤2，直接返回数组长度（任何两个数都构成等差数列） 初始化最大长度为2 创建一个dp数组（或者使用哈希表数组） 遍历所有位置对(i,j)，其中i <j 对于每个位置对，计算公差，更新状态 记录遇到的最大长度 步骤6：示例演示 以nums = [ 3,6,9,12 ]为例： i=0,j=1: d=3，初始长度为2 i=1,j=2: d=3，找到i=0,j=1时公差3的长度为2，所以dp[ 1][ 2 ]=3 i=2,j=3: d=3，找到i=1,j=2时公差3的长度为3，所以dp[ 2][ 3 ]=4 最终得到最大长度为4。 步骤7：复杂度分析 时间复杂度：O(n²)，需要遍历所有位置对 空间复杂度：O(n²)，需要存储所有位置对的状态 这种方法可以有效地找到最长的等差数列子序列，适用于各种规模的输入数组。