最长等差数列¶

最后更新：2023-12-02

链接：

题目描述

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

题目示例

示例 1：示例 2：示例 3：

输入： 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]。

提示：

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

CGolangPythonRustJavaJavaScript

C
#include <stdio.h>
#include <stdlib.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))  

int longestArithSeqLength(int* nums, int numsSize) {  
    if (numsSize <= 2) {  
        return numsSize;  
    }  

    // 创建一个哈希表来存储dp数组  
    // 由于C语言没有内置的哈希表，我们需要使用额外的数据结构  
    // 这里，我们使用一个简单的数组来实现哈希表的功能，但请注意这不是一个真正的哈希实现  
    // 真正的实现可能需要使用结构体和哈希函数  
    // 为简化，我们假设公差d的范围是[-10000, 10000]，这通常足够处理大多数情况  
    // 如果公差范围更大，你需要相应地调整数组大小或使用动态分配  
    #define DIFF_RANGE 20001 // 公差d的范围大小  
    int dp[numsSize][DIFF_RANGE];  
    memset(dp, 0, sizeof(dp));  

    int maxLength = 0;  

    for (int i = 0; i < numsSize; i++) {  
        for (int j = 0; j < i; j++) {  
            int d = nums[i] - nums[j] + 10000; // 将d转换为正数索引  
            dp[i][d] = dp[j][d] + 1;  
            maxLength = MAX(maxLength, dp[i][d]);  
        }  
    }  

    return maxLength + 1;  
}

Go
func longestArithSeqLength(nums []int) int {
    n := len(nums)  
    if n <= 2 {  
        return n  
    }

    // dp[i][d] 表示以 nums[i] 结尾，公差为 d 的最长等差子序列的长度  
    dp := make([]map[int]int, n)  
    maxLength := 1  

    for i := 0; i < n; i++ {
        dp[i] = make(map[int]int)  
        for j := 0; j < i; j++ {  
            d := nums[i] - nums[j] // 计算当前元素与前一个元素的公差  
            dp[i][d] = dp[j][d] + 1 // 更新以 nums[i] 结尾，公差为 d 的等差子序列的长度  
            if dp[i][d] > maxLength {  
                maxLength = dp[i][d] // 更新最长等差子序列的长度  
            }  
        }  
    }  

    return maxLength + 1 
}

Python
class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int: 
        n = len(nums)  
        if n < 2:  
            return n  

        dp = {}  # 外层字典，键是 nums 中的数，值是一个内层字典  
        max_length = 2  

        for i in range(n):  
            curr_map = {}  # 内层字典，键是公差，值是等差数列的长度  
            for j in range(i):  
                diff = nums[i] - nums[j]  
                prev_length = dp.get(nums[j], {}).get(diff, 1) + 1  
                curr_map[diff] = prev_length  
                max_length = max(max_length, prev_length)  
            dp[nums[i]] = curr_map  

        return max_length

Rust
use std::collections::HashMap;

impl Solution {
    pub fn longest_arith_seq_length(nums: Vec<i32>) -> i32 {
        let n = nums.len();  
        if n < 2 {  
            return n as i32;  
        }  

        let mut dp: HashMap<i32, HashMap<i32, i32>> = HashMap::new();  
        let mut max_length = 2;  

        for i in 0..n {  
            let mut curr_map = HashMap::new();  
            for j in 0..i {  
                let diff = nums[i] - nums[j];  
                let prev_length = dp.get(&nums[j]).and_then(|map| map.get(&diff)).unwrap_or(&1) + 1;  
                curr_map.insert(diff, prev_length);  
                max_length = std::cmp::max(max_length, prev_length);  
            }  
            dp.insert(nums[i], curr_map);  
        }  

        max_length  
    }
}

Java
    import java.util.HashMap;  
    import java.util.Map; 

    class Solution {
        public int longestArithSeqLength(int[] nums) {
            int n = nums.length;  
            if (n < 2) {  
                return n;  
            }  
    
            Map<Integer, Map<Integer, Integer>> dp = new HashMap<>();  
            int maxLength = 2;  
    
            for (int i = 0; i < n; i++) {  
                Map<Integer, Integer> currMap = new HashMap<>();  
                for (int j = 0; j < i; j++) {  
                    int diff = nums[i] - nums[j];  
                    int prevLength = (dp.getOrDefault(nums[j], new HashMap<>())).getOrDefault(diff, 1) + 1;  
                    currMap.put(diff, prevLength);  
                    maxLength = Math.max(maxLength, prevLength);  
                }  
                dp.put(nums[i], currMap);  
            }  
    
            return maxLength;  
        }
    }

Text Only

/**  
* @param {number[]} nums  
* @return {number}  
*/  
var longestArithSeqLength = function(nums) {  
const n = nums.length;  
if (n <= 2) return n;  

// dp[i] 是一个哈希表，保存以 nums[i] 结尾的所有等差数列的最长长度  
const dp = new Array(n).fill(null).map(() => new Map());  
let maxLength = 1;  

for (let i = 0; i < n; i++) {  
    for (let j = 0; j < i; j++) {  
    const diff = nums[i] - nums[j];  

    // 尝试将 nums[i] 添加到以 nums[j] 结尾、公差为 diff 的等差数列中  
    const currentLength = dp[j].get(diff) || 0;  
    dp[i].set(diff, currentLength + 1);  

    // 更新最长等差数列的长度  
    maxLength = Math.max(maxLength, currentLength + 1);  
    }  
}  

return maxLength + 1;  
};