最长等差数列 题目描述 给定一个整数数组 nums，返回该数组中最长等差数列的子序列长度。等差数列是指数组中任意相邻两个元素的差相等的序列。子序列不要求连续，但需要保持原始顺序。 示例： 输入：nums = [ 3,6,9,12 ] 输出：4 解释：整个数组就是公差为3的等差数列 输入：nums = [ 9,4,7,2,10 ] 输出：3 解释：最长的等差数列是 [ 4,7,10] 或 [ 9,7,5 ]，长度都是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 的序列，那么 dp[ i][ d] = dp[ j][ d ] + 1 否则，dp[ i][ d] = 2（只有 nums[ j] 和 nums[ i ] 两个元素） 4. 算法步骤 初始化 dp 数组，每个位置对应一个空字典 初始化最大长度 max_ len = 1（单个元素也算等差数列） 遍历 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 5. 示例演示 以 nums = [ 3,6,9,12 ] 为例： i=0: dp[ 0 ] = {}（单个元素） i=1: j=0, d=3, dp[ 1][ 3 ] = 2 max_ len = 2 i=2: j=0, d=6, dp[ 2][ 6 ] = 2 j=1, d=3, dp[ 1]中有3→dp[ 2][ 3] = dp[ 1][ 3 ] + 1 = 3 max_ len = 3 i=3: j=0, d=9, dp[ 3][ 9 ] = 2 j=1, d=6, dp[ 3][ 6 ] = 2 j=2, d=3, dp[ 2]中有3→dp[ 3][ 3] = dp[ 2][ 3 ] + 1 = 4 max_ len = 4 6. 复杂度分析 时间复杂度：O(n²)，需要两重循环 空间复杂度：O(n²)，最坏情况下每个位置可能存储 O(n) 个不同的公差 7. 边界情况处理 空数组返回 0 单元素数组返回 1 所有元素相同的情况（公差为0）也能正确处理 这种解法通过动态规划记录了所有可能的公差序列，确保了找到最长的等差数列。