LeetCode 1027. 最长等差数列

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 1027. 最长等差数列

思路分析

解法一：动态规划（推荐）

核心思路：

设 dp[i][d] 表示以 i 结尾、公差为 d 的最长等差子序列长度。

对每对 (j, i) 更新 dp[i][d] = dp[j][d] + 1。

使用哈希表存储每个 i 的差值状态。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示数组长度。

空间复杂度：O(n^2)，存储所有差值状态。

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        @SuppressWarnings("unchecked")
        Map<Integer, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
        }

        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int d = nums[i] - nums[j];
                int len = dp[j].getOrDefault(d, 1) + 1;
                dp[i].put(d, Math.max(dp[i].getOrDefault(d, 1), len));
                ans = Math.max(ans, dp[i].get(d));
            }
        }

        return ans;
    }
}

func longestArithSeqLength(nums []int) int {
	n := len(nums)
	dp := make([]map[int]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make(map[int]int)
	}

	ans := 0
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			d := nums[i] - nums[j]
			len := dp[j][d]
			if len == 0 {
				len = 1
			}
			len++
			if len > dp[i][d] {
				dp[i][d] = len
			}
			if dp[i][d] > ans {
				ans = dp[i][d]
			}
		}
	}

	return ans
}

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	DP
1218. 最长定差子序列	中等	DP
1027. 最长等差数列	中等	DP
446. 等差数列划分 II - 子序列	困难	DP
413. 等差数列划分	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/41878434