Medium

题目描述

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

注意：

  • 子序列是一个可以从另一个数组派生出来的数组，通过删除某些或不删除元素而不改变其余元素的顺序。
  • 如果 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 <= 1000
  • 0 <= nums[i] <= 500

解题思路

这是一道典型的动态规划题目，关键是找到状态转移的方法。

核心思路： 对于每个位置 i，我们需要考虑以 nums[i] 结尾的所有可能等差数列。由于等差数列的性质，我们可以用公差来唯一确定一个等差数列的特征。

状态定义： 使用 dp[i][d] 表示以 nums[i] 结尾、公差为 d 的等差数列的最大长度。

状态转移： 对于每个位置 i，我们遍历之前的所有位置 j（j < i），计算公差 d = nums[i] - nums[j]。如果之前存在以 nums[j] 结尾、公差为 d 的等差数列，那么我们可以将 nums[i] 添加到该数列末尾，长度加 1。

实现细节：

  • 由于公差可能为负数，我们需要对公差进行偏移处理（加上一个偏移量）
  • 每个等差数列至少有 2 个元素，所以初始长度为 2
  • 最终答案是所有 dp[i][d] 中的最大值

时间复杂度优化： 可以使用哈希表来存储状态，避免数组的空间浪费，特别是当数值范围很大时。

代码实现

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) return n;
        
        vector<vector<int>> dp(n, vector<int>(1001, 1));
        int maxLen = 2;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j] + 500; // 偏移500避免负索引
                dp[i][diff] = dp[j][diff] + 1;
                maxLen = max(maxLen, dp[i][diff]);
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 2:
            return n
        
        dp = [{}] * n
        for i in range(n):
            dp[i] = {}
        
        max_len = 2
        
        for i in range(1, n):
            for j in range(i):
                diff = nums[i] - nums[j]
                dp[i][diff] = dp[j].get(diff, 1) + 1
                max_len = max(max_len, dp[i][diff])
        
        return max_len

public class Solution {
    public int LongestArithSeqLength(int[] nums) {
        int n = nums.Length;
        if (n <= 2) return n;
        
        var dp = new Dictionary<int, int>[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new Dictionary<int, int>();
        }
        
        int maxLen = 2;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                dp[i][diff] = dp[j].GetValueOrDefault(diff, 1) + 1;
                maxLen = Math.Max(maxLen, dp[i][diff]);
            }
        }
        
        return maxLen;
    }
}

var longestArithSeqLength = function(nums) {
    const n = nums.length;
    if (n <= 2) return n;
    
    const dp = Array(n).fill(null).map(() => new Map());
    let maxLen = 2;
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            const diff = nums[i] - nums[j];
            dp[i].set(diff, (dp[j].get(diff) || 1) + 1);
            maxLen = Math.max(maxLen, dp[i].get(diff));
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要遍历所有位置对(i,j)，其中i>j
空间复杂度O(n²)在最坏情况下，每个位置可能存储O(n)个不同的公差

相关题目