1. 题目

2. 解题思路

假设我们以 f[d][nums[i]]表示以 nums[i] 为结尾元素间距为 d 的等差数列的最大长度，那么，如果 nums[i]-d 也存在于 nums 数组中，则有：

$$f[d][nums[i]]=f[d][nums[i]-d]+1$$

否则，$f[d][nums[i]]=1$。

d的取值范围为 $[-(max-min),+(max-min)]$。因为 nums[i]-d 要位于 nums[i] 的前面，所以，针对每一个 d ，我们初始化所有元素为 -1，然后从前往后开始遍历数组，根据上面的公式依次更新 f，其中最大的数值即为所求。

时间复杂度为 $O(d\ast nums.size())$，空间复杂度为 $O(nums.size())$。

3. 代码实现

于是，我开始实现了第一版代码，完全就照着上面的解题思路来写。

class Solution {
public:int longestArithSeqLength(vector<int>& nums) {map<int, map<int, int> > dp;int max_value = 0;int min_value = 500;map<int, int> init_dp;for (size_t i = 0; i < nums.size(); ++i){max_value = max(max_value, nums[i]);min_value = min(min_value, nums[i]);init_dp[nums[i]] = -1;}int diff = max_value - min_value;int ret = 1;for (int d = -diff; d <= diff; ++d) {dp[d] = init_dp;dp[d][nums[0]] = 1;for (size_t i = 1; i < nums.size(); ++i) {if (dp[d].count(nums[i]-d) == 0) {dp[d][nums[i]] = 1;continue;}if (dp[d][nums[i]-d] != -1) {dp[d][nums[i]] = dp[d][nums[i]-d] + 1;ret = max(ret, dp[d][nums[i]]);}else {dp[d][nums[i]] = 1;}}}return ret;}
};

很可惜，没有通过全部测试用例，超时了。

超出时间限制 53 / 65 个通过的测试用例

首先，这里的 dp就是充当哈希表的作用，不需要有序，没有必要用 map，我改成了 unordered_map后，通过了，但是执行用时和消耗内存都排在了末尾。

查看双层 for 循环，针对每一个d，我们其实可以都用同一个哈希表，所以代码作如下修改：

class Solution {
public:int longestArithSeqLength(vector<int>& nums) {int max_value = 0;int min_value = 500;unordered_map<int, int> init_dp;for (size_t i = 0; i < nums.size(); ++i){max_value = max(max_value, nums[i]);min_value = min(min_value, nums[i]);init_dp[nums[i]] = -1;}int diff = max_value - min_value;int ret = 1;for (int d = -diff; d <= diff; ++d) {unordered_map<int, int> dp = init_dp; // 这里每次都用同一个即可dp[nums[0]] = 1;for (size_t i = 1; i < nums.size(); ++i) {if (dp.count(nums[i]-d) == 0) {dp[nums[i]] = 1;continue;}if (dp[nums[i]-d] != -1) {dp[nums[i]] = dp[nums[i]-d] + 1;ret = max(ret, dp[nums[i]]);}else {dp[nums[i]] = 1;}}}return ret;}
};

这样，速度和内存都有所提升，但提升得也非常有限。继续思考，题目中给出了 0 <= nums[i] <= 500 的限制条件，所以 $nums[i]-d\in [0,500]$，如果不在这个范围，肯定是无效的。所以，dp直接就可以用一个大小为 501 的数组来代替了，数组的下标就可以作为索引。

class Solution {
public:int longestArithSeqLength(vector<int>& nums) {int max_value = 0;int min_value = 500;for (size_t i = 0; i < nums.size(); ++i){max_value = max(max_value, nums[i]);min_value = min(min_value, nums[i]);}int diff = max_value - min_value;int ret = 1;for (int d = -diff; d <= diff; ++d) {vector<int> dp(501, -1);dp[nums[0]] = 1;for (size_t i = 1; i < nums.size(); ++i) {if (nums[i]-d < 0 || nums[i]-d > 500) {dp[nums[i]] = 1;continue;}if (dp[nums[i]-d] != -1) {dp[nums[i]] = dp[nums[i]-d] + 1;ret = max(ret, dp[nums[i]]);}else {dp[nums[i]] = 1;}}}return ret;}
};

class Solution:def longestArithSeqLength(self, nums: List[int]) -> int:max_value = max(nums)min_value = min(nums)diff = max_value - min_valueret = 1for d in range(-diff, diff+1):dp = [-1] * 501dp[nums[0]] = 1for i in range(1, len(nums)):if 0 <= nums[i] - d <= 500:dp[nums[i]] = max(dp[nums[i]-d]+1, 1)ret = max(ret, dp[nums[i]])else:dp[nums[i]] = 1return ret