最长等差数列的长度（进阶版——允许公差为负且统计最长等差数列的个数） 题目描述 给定一个整数数组 nums，返回数组中所有最长等差数列的长度之和。注意，等差数列的公差可以是任意整数（包括负数），且至少包含两个元素。如果同一个等差数列以不同起始位置或结束位置出现多次，需要统计多次。 例如：nums = [ 2,4,6,8,10 ] 最长等差数列有：[ 2,4,6,8,10]、[ 4,6,8,10]、[ 2,4,6,8 ]等，但所有最长等差数列的长度都是5，且不同起始位置的最长等差数列个数需要统计。 解题思路 使用动态规划，定义 dp[ i][ d ] 表示以第 i 个元素结尾、公差为 d 的等差数列的最大长度。由于公差可能很大且为负数，我们使用哈希表来存储公差键值对。 步骤讲解 状态定义 设 dp[ i] 是一个字典（哈希表），键是公差 d，值是以 nums[ i ] 结尾、公差为 d 的等差数列的最大长度。 同时，我们定义 count[ i] 也是一个字典，键是公差 d，值是以 nums[ i ] 结尾、公差为 d 的最长等差数列的个数。 状态转移 对于每个 i（从 0 到 n-1），遍历所有 j < i： 计算公差 d = nums[ i] - nums[ j ] 如果 dp[ j] 中存在公差 d，则说明可以在以 nums[ j] 结尾的公差为 d 的数列后接上 nums[ i ]，因此： dp[ i][ d] = dp[ j][ d ] + 1 同时，count[ i][ d] 继承 count[ j][ d ]（因为每个以 j 结尾的数列延长到 i 都形成新数列） 如果 dp[ j ] 中没有公差 d，则说明从 j 到 i 可以形成一个长度为 2 的新等差数列： dp[ i][ d ] = 2 count[ i][ d ] = 1（新增一个数列） 注意：可能存在多个 j 得到相同的 d，此时需要累加 count[ i][ d ]。 记录最大值和总数 在遍历过程中记录全局最大长度 max_ len。 最后，遍历所有 i 和 d，如果 dp[ i][ d] == max_ len，则将对应的 count[ i][ d ] 累加到结果中。 初始化 每个位置 i 的 dp[ i] 和 count[ i ] 初始为空字典。 最大长度 max_ len 初始为 0（至少两个元素，所以最小可能max_ len是2）。 举例说明 以 nums = [ 2,4,6,8,10 ] 为例： i=0: 无 j<0，dp[ 0 ] 为空 i=1: j=0, d=2，新增长度为2的数列，dp[ 1][ 2]=2, count[ 1][ 2 ]=1 i=2: j=0, d=4，新增长度为2的数列，dp[ 2][ 4]=2, count[ 2][ 4 ]=1 j=1, d=2，继承 j=1 的数列，dp[ 2][ 2]=dp[ 1][ 2]+1=3, count[ 2][ 2 ]=1 继续遍历，最终所有公差为2的数列长度达到5，且每个起始位置都不同，统计个数。 复杂度分析 时间复杂度 O(n²)，空间复杂度 O(n²)（最坏情况下每个 i 有 O(i) 个公差）。 通过以上步骤，我们可以正确统计所有最长等差数列的个数。