原文链接: https://leetcode-cn.com/problems/longest-arithmetic-subsequence

英文原文

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Recall that a subsequence of an array nums is a list nums[i1], nums[i2], ..., nums[ik] with 0 <= i1 < i2 < ... < ik <= nums.length - 1, and that a sequence seq is arithmetic if seq[i+1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

 

Example 1:

Input: nums = [3,6,9,12]
Output: 4
Explanation: 
The whole array is an arithmetic sequence with steps of length = 3.

Example 2:

Input: nums = [9,4,7,2,10]
Output: 3
Explanation: 
The longest arithmetic subsequence is [4,7,10].

Example 3:

Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation: 
The longest arithmetic subsequence is [20,15,10,5].

 

Constraints:

• 2 <= nums.length <= 1000
• 0 <= nums[i] <= 500

中文题目

给定一个整数数组 A，返回 A 中最长等差子序列的长度。

回想一下，A 的子序列是列表 A[i_1], A[i_2], ..., A[i_k] 其中 0 <= i_1 < i_2 < ... < i_k <= A.length - 1。并且如果 B[i+1] - B[i]( 0 <= i < B.length - 1) 的值都相同，那么序列 B 是等差的。

 

示例 1：

输入：[3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。

示例 2：

输入：[9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。

示例 3：

输入：[20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。

 

提示：

1. 2 <= A.length <= 2000
2. 0 <= A[i] <= 10000

通过代码

高赞题解

解题思路1

无优化的动态规划。由于至少两个元素才能定义等差数列，所以定义状态dp[i][j]为以A[i]和A[j]为最后两个元素的等差数列的长度。

那么最后两个数定了，前一个元素也就定了为target = 2 * dp[i] - dp[j]， 只需要找到i前面最靠近i的target的位置即可。

$$dp[i][j] = dp[id_{target}][i] + 1$$

所以可以使用三重循环来做，时间复杂度为O(n^3)

代码1

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        unordered_map<int, int> mp;
        int n = A.size();
        for (int i = n - 1; i >= 0; i --) mp[A[i]] = i;
        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 * A[i] - A[j];
                for (int k = i - 1; k >= 0; k --) {
                    if (A[k] == target) {
                        dp[i][j] = dp[k][i] + 1;
                        break;
                    }
                }
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};

解题思路2:优化版

通过对上面代码进行观察，可以发现，内部的第三重循环可以使用哈希表来优化。

通过一个哈希表记录每个在i之前的数出现的最后一个下标，就可以在O(1)的时间内找到target所在的下标。

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

个人博客

代码2

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        unordered_map<int, int> mp;
        int n = A.size();
        // for (int i = n - 1; i >= 0; i --) mp[A[i]] = i;
        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 * A[i] - A[j];
                if (mp.count(target)) dp[i][j] = dp[mp[target]][i] + 1;
                ans = max(ans, dp[i][j]);
            }
            mp[A[i]] = i;
        }
        return ans;
    }
};

统计信息

通过次数	提交次数	AC比率
14010	32346	43.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言