阅读目录
- 1. 题目
- 2. 解题思路
- 3. 代码实现
1. 题目
2. 解题思路
假设我们以 f[d][nums[i]]表示以 nums[i] 为结尾元素间距为 d 的等差数列的最大长度，那么，如果 nums[i]-d 也存在于 nums 数组中，则有：
f [ d ] [ n u m s [ i ] ] = f [ d ] [ n u m s [ i ] − d ] + 1 f[d][nums[i]]=f[d][nums[i]-d]+1 f[d][nums[i]]=f[d][nums[i]−d]+1
否则， f [ d ] [ n u m s [ i ] ] = 1 f[d][nums[i]]=1 f[d][nums[i]]=1。
d的取值范围为
[
−
(
m
a
x
−
m
i
n
)
,
+
(
m
a
x
−
m
i
n
)
]
[-(max-min), +(max-min)]
[−(max−min),+(max−min)]。因为 nums[i]-d 要位于 nums[i] 的前面，所以，针对每一个 d ，我们初始化所有元素为 -1，然后从前往后开始遍历数组，根据上面的公式依次更新 f，其中最大的数值即为所求。
时间复杂度为 O ( d ∗ n u m s . s i z e ( ) ) O(d*nums.size()) O(d∗nums.size())，空间复杂度为 O ( n u m s . s i z e ( ) ) O(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 的限制条件，所以
n
u
m
s
[
i
]
−
d
∈
[
0
,
500
]
nums[i]-d\in[0,500]
nums[i]−d∈[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_value
ret = 1
for d in range(-diff, diff+1):
dp = [-1] * 501
dp[nums[0]] = 1
for 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]] = 1
return ret
