LeetCode 题解工作台
统计特殊子序列的数目
特殊序列 是由 正整数 个 0 ，紧接着 正整数 个 1 ，最后 正整数 个 2 组成的序列。 比方说， [0,1,2] 和 [0,0,1,1,1,2] 是特殊序列。 相反， [2,1,0] ， [1] 和 [0,1,2,0] 就不是特殊序列。 给你一个数组 nums （ 仅 包含整数 0 ， 1 …
2
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们定义 表示前 个元素中，以 结尾的特殊子序列的个数。初始时 ，如果 ，则 。 对于 $i \gt 0$，我们考虑 的值：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
特殊序列 是由 正整数 个 0 ，紧接着 正整数 个 1 ，最后 正整数 个 2 组成的序列。
- 比方说，
[0,1,2]和[0,0,1,1,1,2]是特殊序列。 - 相反，
[2,1,0]，[1]和[0,1,2,0]就不是特殊序列。
给你一个数组 nums （仅 包含整数 0，1 和 2），请你返回 不同特殊子序列的数目 。由于答案可能很大，请你将它对 109 + 7 取余 后返回。
一个数组的 子序列 是从原数组中删除零个或者若干个元素后，剩下元素不改变顺序得到的序列。如果两个子序列的 下标集合 不同，那么这两个子序列是 不同的 。
示例 1：
输入：nums = [0,1,2,2] 输出：3 解释：特殊子序列为 [0,1,2,2]，[0,1,2,2] 和 [0,1,2,2] 。
示例 2：
输入：nums = [2,2,0,0] 输出：0 解释：数组 [2,2,0,0] 中没有特殊子序列。
示例 3：
输入：nums = [0,1,2,0,1,2] 输出：7 解释：特殊子序列包括： - [0,1,2,0,1,2] - [0,1,2,0,1,2] - [0,1,2,0,1,2] - [0,1,2,0,1,2] - [0,1,2,0,1,2] - [0,1,2,0,1,2] - [0,1,2,0,1,2]
提示：
1 <= nums.length <= 1050 <= nums[i] <= 2
解题思路
方法一：动态规划
我们定义 表示前 个元素中，以 结尾的特殊子序列的个数。初始时 ，如果 ，则 。
对于 ，我们考虑 的值：
如果 ：如果我们不选择 ，则 ；如果我们选择 ，那么 ，因为我们可以在任何一个以 结尾的特殊子序列后面加上一个 得到一个新的特殊子序列，也可以将 单独作为一个特殊子序列。因此 。其余的 与 相等。
如果 ：如果我们不选择 ，则 ；如果我们选择 ，那么 ，因为我们可以在任何一个以 或 结尾的特殊子序列后面加上一个 得到一个新的特殊子序列。因此 。其余的 与 相等。
如果 ：如果我们不选择 ，则 ；如果我们选择 ，那么 ，因为我们可以在任何一个以 或 结尾的特殊子序列后面加上一个 得到一个新的特殊子序列。因此 。其余的 与 相等。
综上，我们可以得到如下的状态转移方程：
最终的答案即为 。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def countSpecialSubsequences(self, nums: List[int]) -> int:
mod = 10**9 + 7
n = len(nums)
f = [[0] * 3 for _ in range(n)]
f[0][0] = nums[0] == 0
for i in range(1, n):
if nums[i] == 0:
f[i][0] = (2 * f[i - 1][0] + 1) % mod
f[i][1] = f[i - 1][1]
f[i][2] = f[i - 1][2]
elif nums[i] == 1:
f[i][0] = f[i - 1][0]
f[i][1] = (f[i - 1][0] + 2 * f[i - 1][1]) % mod
f[i][2] = f[i - 1][2]
else:
f[i][0] = f[i - 1][0]
f[i][1] = f[i - 1][1]
f[i][2] = (f[i - 1][1] + 2 * f[i - 1][2]) % mod
return f[n - 1][2]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for a single pass through nums. Space complexity is O(1) since only three counters are maintained regardless of array size. Modular arithmetic does not affect asymptotic complexity. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for an O(n) solution using dynamic programming states.
- question_mark
Expect candidate to handle large array sizes efficiently with modulo arithmetic.
- question_mark
Check if candidate recognizes sequence constraints of 0s, 1s, then 2s.
常见陷阱
外企场景- error
Updating counts in wrong order, corrupting state transitions.
- error
Forgetting to apply modulo 10^9 + 7 leading to overflow.
- error
Miscounting subsequences by treating repeated elements incorrectly.
进阶变体
外企场景- arrow_right_alt
Count special subsequences allowing zeros to repeat after 2s.
- arrow_right_alt
Count sequences with 0,1,2,3 using similar state transitions.
- arrow_right_alt
Find longest special subsequence instead of total count.