难度: Medium
给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。
示例 1：
输入：nums = [3,6,9,12] 输出：4 解释： 整个数组是公差为 3 的等差数列。
示例 2：
输入：nums = [9,4,7,2,10] 输出：3 解释： 最长的等差子序列是 [4,7,10]。
示例 3：
输入：nums = [20,1,15,3,10,5,8] 输出：4 解释： 最长的等差子序列是 [20,15,10,5]。
提示：
2 <= nums.length <= 10000 <= nums[i] <= 500运行时间: 534 ms
内存: 25.3 MB
class Solution:
def longestArithSeqLength(self, nums: List[int]) -> int:
ans = 2
dp = {}
for a in nums:
flag = False
if a not in dp:
dp[a] = {}
flag = True
for b in dp:
if b==a and flag: continue
d = a - b
if d in dp[b]:
dp[a][d] = dp[b][d] + 1
ans = max(ans, dp[a][d])
else:
dp[a][d] = 2
return ans
本题解使用了动态规划的方法。定义一个字典`dp`，其中`dp[a][d]`表示以数字`a`结尾，公差为`d`的最长等差子序列的长度。遍历数组中的每个数字`a`，对于每个数字，再从之前遍历过的数字中选择一个数字`b`，计算公差`d = a - b`。如果这个公差在`dp[b]`中已存在，则说明可以在以`b`结尾，公差为`d`的子序列后追加`a`，形成更长的子序列。否则，以`a`和`b`可以形成一个新的长度为2的子序列。通过这种方式，可以更新`dp[a][d]`的值，并记录过程中出现的最大长度。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def longestArithSeqLength(self, nums: List[int]) -> int:
ans = 2 # 初始化答案为2，因为任意两个数都可以形成长度为2的等差数列
dp = {} # dp字典，用于存储以每个数结尾的等差序列的长度
for a in nums: # 遍历数组中的每个数a
flag = False # 标记变量，用于处理特殊情况，避免自身对自身的处理
if a not in dp:
dp[a] = {} # 如果a不在dp中，初始化一个新的字典
flag = True
for b in dp: # 遍历之前的所有数b
if b == a and flag: continue # 避免自身对自身的处理
d = a - b # 计算公差d
if d in dp[b]: # 如果dp[b]已经有公差d
dp[a][d] = dp[b][d] + 1 # 更新dp[a][d]
ans = max(ans, dp[a][d]) # 更新最大长度
else:
dp[a][d] = 2 # 初始化公差为d的等差序列长度
return ans # 返回最长等差数列的长度
在动态规划的解法中，`dp`字典是用来存储以不同数值作为结尾，且具有不同公差的等差子序列的最大长度。具体到初始化，对于数组中每个新出现的数`a`，如果`a`不在`dp`中，就会为`a`创建一个新的空字典，这个字典将存储以`a`为结尾且具有各种公差`d`的子序列长度。当遇到新的公差`d`时，如果在`dp[b]`中已经存在公差`d`，则`dp[a][d]`被设置为`dp[b][d] + 1`，表示在以`b`为结尾的等差子序列后添加`a`，形成更长的序列。如果`dp[b]`中不存在公差`d`，则表示`a`和`b`可以形成一个新的长度为2的等差子序列，此时`dp[a][d]`被初始化为2。
在遍历元素`b`时，特别判断`b == a`并跳过处理是为了避免将元素`a`与其自身进行比较。如果不做这种判断，那么当`a`和`b`相同时，公差`d`将计算为0，这会导致以`a`为结尾的等差子序列错误地考虑自身作为序列的一部分。这种自引用会造成算法结果的不准确，因为等差数列的定义要求至少包含两个不同的元素。因此，这样的处理确保了算法的正确性，使得每个等差数列至少包含两个独立的元素。
在这种方法中，处理数组`nums`中重复的数字不会导致除0错误或其他问题。算法在计算公差`d = a - b`时，如果`a`与`b`相同，确实会产生0的公差，但这并不会引起除0错误，因为这里没有进行除法运算。相反，公差为0的情况意味着在数组中存在重复的数字，这些数字可以形成公差为0的等差数列。因此，算法能够正确处理重复数字，只要遵循逻辑确保不重复计算同一元素对自身的公差即可。