最长等差数列

发表于 分类于 ， 阅读次数： Waline： 本文字数： 2.2k 阅读时长 ≈ 2 分钟

1027. 最长等差数列

给你一个整数数组 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 是等差的。

示例：

输入：nums = [3,6,9,12]

输出：4

解释：

整个数组是公差为 3 的等差数列。

输入：nums = [9,4,7,2,10]

输出：3

解释：

最长的等差子序列是 [4,7,10]。

输入：nums = [20,1,15,3,10,5,8]

输出：4

解释：

最长的等差子序列是 [20,15,10,5]。

思路：

由于最少需要两个元素才能定义等差数列，所以定义状态dp[i][j]为nums[i]和nums[j]为最后两个元素的等差数列的长度。

根据等差数列的性质，如果最后两个数定了，那么前一个元素也就确定了，target = 2 * nums[i] - nums[j]，

例如：

nums = [9,4,7,2,10]

例如我们现在nums[i] = 4,nums[j] = 10，把么下一个可以构成等差数列的数就是2 * 4 - 10 = 4

然后查找i前面是否存在这样一个元素即可。

dp[i][j] = dp[ID_target][i] + 1

所以可以选择三重循环来解决。时间复杂度为O(N^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        //dp[i][j]表示以 nums[i] 和 nums[j] 为最后两个元素的等差数列长度
        int n = nums.size();
       //base case
        vector<vector<int> > dp(n, vector<int>(n,2));
        int ans = 0;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                int target = 2 * nums[i] - nums[j];
                for(int k = i - 1; k >= 0; k--){
                    if(nums[k] == target){
                        dp[i][j] = dp[k][i] + 1;
                        break;
                    }
                }
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};

我们还有优化的空间吗？可以看到内部的第三重循环可以使用哈希表来优化，通过一个哈希表记录每个在i之前的数出现的最后一个下标，就可以在O(1)的时间内找到target所在的下标。

时间复杂度为O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        unordered_map<int,int> mp;
        int n = nums.size();
        vector<vector<int> > dp(n, vector<int>(n, 2));
        int res = 0;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                int target = 2 * nums[i] - nums[j];
                if(mp.count(target)) dp[i][j] = dp[mp[target]][i] + 1;
                res = max(res, dp[i][j]);
            }
            mp[nums[i]] = i;
        }
        return res;
    }
};