最长等差数列

1027. 最长等差数列

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

回想一下，nums 的子序列是一个列表 nums[i₁], nums[i₂], ..., nums[i_k] ，且 0 <= i₁ < i₂ < ... < i_k <= nums.length - 1。并且如果 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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int longestArithSeqLength(vector<int>& nums) { } };

python3 解法, 执行用时: 948 ms, 内存消耗: 22.9 MB, 提交时间: 2023-04-22 11:12:08

class Solution:
    def longestArithSeqLength(self, a: List[int]) -> int:
        ans, max_d = 0, max(a) - min(a)
        f = [[0] * (max_d * 2 + 1) for _ in range(len(a))]
        for i, x in enumerate(a):
            for j in range(i - 1, -1, -1):
                d = x - a[j]  # 公差
                if f[i][d] == 0:
                    f[i][d] = f[j][d] + 1  # 默认的 1 在下面返回时加上
                    if f[i][d] > ans:
                        ans = f[i][d]
        return ans + 1

java 解法, 执行用时: 29 ms, 内存消耗: 50.1 MB, 提交时间: 2023-04-22 11:11:23

class Solution {
    public int longestArithSeqLength(int[] a) {
        int ans = 0, n = a.length;
        var f = new int[n][1001];
        for (int i = 1; i < n; ++i)
            for (int j = i - 1; j >= 0; --j) {
                int d = a[i] - a[j] + 500; // +500 防止出现负数
                if (f[i][d] == 0) {
                    f[i][d] = f[j][d] + 1; // 默认的 1 在下面返回时加上
                    ans = Math.max(ans, f[i][d]);
                }
            }
        return ans + 1;
    }
}

golang 解法, 执行用时: 28 ms, 内存消耗: 16.2 MB, 提交时间: 2023-04-22 11:11:07

func longestArithSeqLength(a []int) (ans int) {
    n := len(a)
    f := make([][1001]int, n)
    for i := 1; i < n; i++ {
        for j := i - 1; j >= 0; j-- {
            d := a[i] - a[j] + 500 // +500 防止出现负数
            if f[i][d] == 0 {
                f[i][d] = f[j][d] + 1 // 默认的 1 在下面返回时加上
                ans = max(ans, f[i][d])
            }
        }
    }
    return ans + 1
}

func max(a, b int) int { if a < b { return b }; return a }

golang 解法, 执行用时: 460 ms, 内存消耗: 18.9 MB, 提交时间: 2023-04-22 10:54:15

func longestArithSeqLength(a []int) (ans int) {
    n := len(a)
    maxLen := make([]map[int]int, n)
    var dfs func(int) map[int]int
    dfs = func(i int) map[int]int {
        if maxLen[i] != nil { // 之前算过了
            return maxLen[i]
        }
        maxLen[i] = map[int]int{}
        for j := i - 1; j >= 0; j-- {
            d := a[i] - a[j] // 公差
            if maxLen[i][d] == 0 {
                maxLen[i][d] = dfs(j)[d] + 1 // 默认的 1 在下面返回时加上
                ans = max(ans, maxLen[i][d])
            }
        }
        return maxLen[i]
    }
    for i := 1; i < n; i++ {
        dfs(i)
    }
    return ans + 1
}

func max(a, b int) int { if a < b { return b }; return a }

java 解法, 执行用时: 357 ms, 内存消耗: 64.3 MB, 提交时间: 2023-04-22 10:53:57

class Solution {
    private Map<Integer, Integer>[] maxLen;
    private int[] a;
    private int ans;

    public int longestArithSeqLength(int[] nums) {
        a = nums;
        int n = a.length;
        maxLen = new HashMap[n];
        for (int i = 1; i < n; ++i)
            dfs(i);
        return ans;
    }

    private Map<Integer, Integer> dfs(int i) {
        if (maxLen[i] != null) return maxLen[i]; // 之前算过了
        // i=0 时不会进入循环
        maxLen[i] = new HashMap<>();
        for (int j = i - 1; j >= 0; --j) {
            int d = a[i] - a[j]; // 公差
            if (!maxLen[i].containsKey(d)) {
                maxLen[i].put(d, dfs(j).getOrDefault(d, 1) + 1);
                ans = Math.max(ans, maxLen[i].get(d));
            }
        }
        return maxLen[i];
    }
}

python3 解法, 执行用时: 1096 ms, 内存消耗: 104 MB, 提交时间: 2023-04-22 10:53:38

class Solution:
    def longestArithSeqLength(self, a: List[int]) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果
        def dfs(i: int) -> dict[int, int]:
            # i=0 时不会进入循环，返回空哈希表
            max_len = {}
            for j in range(i - 1, -1, -1):
                d = a[i] - a[j]  # 公差
                if d not in max_len:
                    max_len[d] = dfs(j).get(d, 1) + 1
            return max_len
        return max(max(dfs(i).values()) for i in range(1, len(a)))

上一题

下一题

详情