最长等差数列 题目描述 给定一个整数数组 nums ，返回数组中最长等差数列的子序列长度。等差数列是指相邻元素的差相等的序列，子序列不要求连续，但需保持原顺序。例如， [3, 6, 9, 12] 是公差为 3 的等差数列。若数组本身无重复元素，则最短等差数列长度为 2（任意两个元素均构成等差数列）。 解题过程 问题分析 目标：找到最长的等差数列子序列（允许不连续）。 关键变量：公差 diff 决定序列性质，需动态记录以每个元素结尾、不同公差下的最长序列长度。 难点：公差可能为负数或零，需统一处理。 动态规划定义 定义 dp[i][diff] 表示以 nums[i] 结尾、公差为 diff 的最长等差数列长度。 由于公差可能非常大，使用哈希表嵌套存储： dp[i] 是一个字典，键为公差，值为长度。 初始状态：每个元素自身至少构成长度为 1 的序列，但题目要求长度 ≥ 2，因此最终结果需判断是否大于 1。 状态转移方程 遍历每一对 (j, i) （其中 0 ≤ j < i ），计算公差 diff = nums[i] - nums[j] 。 若 dp[j] 中存在键 diff ，说明 nums[j] 已属于某个公差为 diff 的序列，则延长该序列： dp[i][diff] = dp[j][diff] + 1 若 dp[j] 中无该公差，则 nums[j] 和 nums[i] 构成新序列： dp[i][diff] = 2 更新全局最大值 max_len 。 优化与细节 复杂度：双重循环 O(n²) ，哈希操作均摊 O(1) ，总复杂度 O(n²) 。 边界情况：数组长度小于 2 时直接返回长度。 存储优化：只需记录当前 dp[i] 和全局最大值，无需保留全部历史状态。 示例演示 以 nums = [3, 6, 9, 12] 为例： i=1 ： j=0 ， diff=3 ， dp[1][3] = 2 i=2 ： j=0 得 diff=6 ，新序列； j=1 得 diff=3 ，延续序列得 dp[2][3] = dp[1][3] + 1 = 3 i=3 ： j=2 得 diff=3 ， dp[3][3] = dp[2][3] + 1 = 4 最终结果 max_len = 4 。 总结 通过动态规划记录以每个元素结尾的不同公差序列长度，利用哈希表灵活处理任意公差，最终得到最长等差数列子序列。