What is the Longest Arithmetic Subsequence problem about?

It asks for the length of the longest subsequence in an array where consecutive elements have the same difference.

How does the array scanning plus hash lookup pattern apply here?

It lets you track subsequence lengths by difference efficiently, updating counts without recomputing existing sequences.

Can the subsequence be non-contiguous?

Yes, elements do not need to be next to each other as long as the arithmetic difference is consistent.

What is the time complexity of the standard solution?

The approach that scans all pairs and uses hash maps has O(n^2) time complexity.

How do negative or large differences affect the solution?

All differences, including negative or large ones, are stored in the hash map for each element, ensuring correctness regardless of step size.

#1027

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

最长等差数列

给你一个整数数组 nums ，返回 nums 中最长等差子序列的长度。回想一下， nums 的子序列是一个列表 nums[i 1 ], nums[i 2 ], ..., nums[i k ] ，且 0 1 2 k 。并且如果 seq[i+1] - seq[i] ( 0 ) 的值都相同，那么序列…

数组哈希表二分查找动态规划

题目描述

给你一个整数数组 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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示以 $nums[i]$ 结尾且公差为 $j$ 的等差数列的最大长度。初始时 $f[i][j]=1$ ，即每个元素自身都是一个长度为 $1$ 的等差数列。

由于公差可能为负数，且最大差值为 $500$ ，因此，我们可以将统一将公差加上 $500$ ，这样公差的范围就变成了 $[0, 1000]$ 。

考虑 $f[i]$ ，我们可以枚举 $nums[i]$ 的前一个元素 $nums[k]$ ，那么公差 $j=nums[i]-nums[k]+500$ ，此时有 $f[i][j]=\max(f[i][j], f[k][j]+1)$ ，然后我们更新答案 $ans=\max(ans, f[i][j])$ 。

最后返回答案即可。

如果初始时 $f[i][j]=0$ ，那么我们需要在最后返回答案时加上 $1$ 。

时间复杂度 $O(n \times (d + n))$ ，空间复杂度 $O(n \times d)$ 。其中 $n$ 和 $d$ 分别是数组 $nums$ 的长度以及数组 $nums$ 中元素的最大值与最小值的差值。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        n = len(nums)
        f = [[1] * 1001 for _ in range(n)]
        ans = 0
        for i in range(1, n):
            for k in range(i):
                j = nums[i] - nums[k] + 500
                f[i][j] = max(f[i][j], f[k][j] + 1)
                ans = max(ans, f[i][j])
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n^2) due to scanning all pairs of elements, and space complexity is O(n*d) because each element maintains a hash map of differences to subsequence lengths, where d is the number of unique differences in the array.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks about hash map usage for tracking differences
question_mark
Tests understanding of DP and subsequence extension
question_mark
Probes for handling large arrays within constraints

warning

常见陷阱

外企场景

error
Not updating the hash map correctly for each difference
error
Assuming subsequences must be contiguous
error
Overlooking large differences or negative steps in subsequences

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the longest arithmetic subsequence with a fixed common difference
arrow_right_alt
Return the actual longest arithmetic subsequence, not just length
arrow_right_alt
Handle sequences where elements can repeat

help

常见问题

外企场景

继续练习

#792 匹配子序列的单词数 #1477 找两个和为目标值且不重叠的子数组 #2008 出租车的最大盈利