What is the main strategy to solve Arithmetic Slices II - Subsequence efficiently?

Use state transition dynamic programming with hash maps to track differences and extend subsequences, counting only those with length >= 3.

How do I handle duplicates in nums when counting subsequences?

Accumulate counts carefully in the DP maps to avoid double-counting, treating each index separately even if values repeat.

Does the difference need to be positive for arithmetic subsequences?

No, differences can be negative or zero. The key requirement is consistency between consecutive elements.

Can subsequences be non-contiguous?

Yes, subsequences are formed by removing zero or more elements without reordering, so they can skip elements in nums.

What is a common failure mode in interviews for this problem?

Forgetting to exclude subsequences shorter than 3 or mishandling duplicates is a frequent mistake that leads to wrong counts.

#446

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

等差数列划分 II - 子序列

给你一个整数数组 nums ，返回 nums 中所有等差子序列的数目。如果一个序列中至少有三个元素，并且任意两个相邻元素之差相同，则称该序列为等差序列。例如， [1, 3, 5, 7, 9] 、 [7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。再例如， [1…

数组动态规划

题目描述

给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。

如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。

例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
再例如，[1, 1, 2, 5, 7] 不是等差序列。

数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。

例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

题目数据保证答案是一个 32-bit 整数。

示例 1：

输入：nums = [2,4,6,8,10]
输出：7
解释：所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

示例 2：

输入：nums = [7,7,7,7,7]
输出：16
解释：数组中的任意子序列都是等差子序列。

提示：

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1

lightbulb

解题思路

方法一：动态规划 + 哈希表

我们定义 $f[i][d]$ 表示以 $nums[i]$ 为结尾，公差为 $d$ 的弱等差子序列（最少有两个元素）的个数。由于 $d$ 的范围很大，所以我们使用哈希表来统计。

接下来，我们枚举 $nums$ 中的所有元素对 $(nums[i], nums[j])$ ，其中 $j \lt i$ 。我们将其作为等差数列的最后两个元素，由此即可得到公差 $d = nums[i] - nums[j]$ 。由于公差相同，我们可以将 $nums[i]$ 加到以 $nums[j]$ 为结尾的弱等差子序列的末尾，此时以 $nums[i]$ 为结尾的等差子序列的数量为 $f[j][d]$ ，我们将其加入答案。然后，我们再将 $nums[i]$ 加到以 $nums[j]$ 为结尾的弱等差子序列的末尾，这对应着状态转移 $f[i][d] += f[j][d]$ 。同时， $(nums[i], nums[j])$ 这一对元素也可以当作一个弱等差子序列，因此有状态转移 $f[i][d] += f[j][d] + 1$ 。

枚举结束，返回答案即可。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        f = [defaultdict(int) for _ in nums]
        ans = 0
        for i, x in enumerate(nums):
            for j, y in enumerate(nums[:i]):
                d = x - y
                ans += f[j][d]
                f[i][d] += f[j][d] + 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n^2) due to examining all pairs for differences. Space complexity is O(n * m) where m is the average number of distinct differences tracked per index. Efficient hash map usage prevents unnecessary overhead.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to mention dynamic programming with difference tracking immediately.
question_mark
Look for recognition that subsequences of length 2 are building blocks for length >= 3 sequences.
question_mark
Candidates should handle large integers and duplicates to avoid incorrect counting.

warning

常见陷阱

外企场景

error
Counting all subsequences including those shorter than 3, inflating the result.
error
Overwriting counts instead of accumulating, leading to missed sequences.
error
Failing to handle duplicate elements properly, causing double-counting or omission.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the number of arithmetic subsequences with a fixed target difference.
arrow_right_alt
Find the longest arithmetic subsequence instead of total count.
arrow_right_alt
Count arithmetic subsequences modulo a large prime to prevent overflow.

help

常见问题

外企场景

继续练习

#435 无重叠区间 #472 连接词 #473 火柴拼正方形