最长等差数列的长度 题目描述 给定一个整数数组 nums，返回数组中最长等差数列的长度。等差数列是指数组中任意相邻两个元素的差值相等的子序列。注意：这个子序列不要求连续，但必须保持原始顺序。 示例： 输入：nums = [ 3,6,9,12 ] 输出：4 解释：整个数组就是等差数列，公差为3。 输入：nums = [ 9,4,7,2,10 ] 输出：3 解释：最长的等差数列是 [ 4,7,10 ]，公差为3。 解题过程 1. 问题分析 我们需要找到最长的等差数列子序列。关键观察是：等差数列由"公差"和结尾元素决定。如果我们知道以某个元素结尾、具有特定公差的等差数列长度，就能递推得到更长的序列。 2. 状态定义 定义 dp[ i][ d ] 表示以第 i 个元素结尾、公差为 d 的等差数列的最大长度。 但公差 d 可能很大，直接作为数组下标不现实。我们可以用哈希表来存储： dp[ i] = 一个哈希表，键是公差 d，值是以 nums[ i ] 结尾、公差为 d 的等差数列长度。 3. 状态转移 对于每个位置 i，我们检查所有前面的位置 j (0 ≤ j < i)： 计算公差 d = nums[ i] - nums[ j ] 如果 dp[ j] 中有键 d，说明存在以 nums[ j ] 结尾、公差为 d 的等差数列 那么以 nums[ i] 结尾、公差为 d 的等差数列长度 = dp[ j][ d ] + 1 如果 dp[ j] 中没有键 d，说明这是新的等差数列，长度为 2（nums[ j] 和 nums[ i ]） 4. 初始化 每个单独的元素可以视为长度为1的等差数列。对于任意的 i，dp[ i ] 初始化为空哈希表。 5. 算法步骤 初始化最大长度 max_ len = 1（至少为1） 创建 dp 数组，长度为 n，每个元素是空哈希表 遍历 i 从 0 到 n-1： 遍历 j 从 0 到 i-1： 计算公差 d = nums[ i] - nums[ j ] 如果 dp[ j ] 中存在键 d： dp[ i][ d] = dp[ j][ d ] + 1 否则： dp[ i][ d ] = 2 更新 max_ len = max(max_ len, dp[ i][ d ]) 返回 max_ len 6. 示例演示 以 nums = [ 3,6,9,12 ] 为例： i=0: dp[ 0 ] = {} (只有一个元素) i=1: j=0: d=6-3=3, dp[ 0]无3 → dp[ 1][ 3]=2, max_ len=2 i=2: j=0: d=9-3=6, dp[ 0]无6 → dp[ 2][ 6 ]=2 j=1: d=9-6=3, dp[ 1]有3=2 → dp[ 2][ 3]=2+1=3, max_ len=3 i=3: j=0: d=12-3=9, dp[ 0]无9 → dp[ 3][ 9 ]=2 j=1: d=12-6=6, dp[ 1]无6 → dp[ 3][ 6 ]=2 j=2: d=12-9=3, dp[ 2]有3=3 → dp[ 3][ 3]=3+1=4, max_ len=4 最终结果为4。 7. 复杂度分析 时间复杂度：O(n²)，需要两重循环 空间复杂度：O(n²)，最坏情况下每个dp[ i ]可能存储O(n)个不同的公差 8. 边界情况处理 空数组返回0 单元素数组返回1 有重复元素时，公差可能为0，算法能正确处理