0446. Arithmetic Slices II - Subsequence¶
题目信息¶
- 题号:
0446
- 难度:
Hard
- 主题:
子序列、等差数列、长度至少三、按下标计数
- 原题:
- 重点:
子序列不要求连续但必须保持下标顺序、相邻差值固定、不同下标选择分别计数
题目重述¶
给定整数数组 nums,统计其中长度至少为 3 的等差子序列数量。子序列通过删除任意数量元素得到,保留元素的下标顺序不能改变,但它们在原数组中不必连续。
一个子序列是等差序列,当且仅当任意相邻两项的差值都相同。由不同下标集合形成的子序列需要分别计数,即使它们的数值序列完全相同。nums.length 位于 [1, 1000],元素在 32 位有符号整数范围内,题目保证最终答案适合 32 位有符号整数。
自建示例¶
连续数组中存在三条等差子序列:
输入:nums = [1, 3, 5, 7]
输出:3
解释:合法子序列为 [1,3,5]、[3,5,7] 和 [1,3,5,7]。
重复值按下标组合计数:
输入:nums = [2, 2, 2, 2]
输出:5
解释:任取三个下标有 4 种,取全部四个下标有 1 种;它们的公差都为 0,总计 5 条。
按结尾位置和公差累积子序列¶
设 dp[i][d] 表示以 nums[i] 结尾、公差为 d、长度至少为 2 的等差子序列数量。枚举前一个下标 j < i,令 d = nums[i] - nums[j]:单独的二元组 (j, i) 给 dp[i][d] 增加 1,而所有已经以 j 结尾且公差相同的序列都可以追加 nums[i],其中长度至少为 2 的部分会形成题目要求的长度至少为 3 的答案。
差值必须使用 long long,因为两个 32 位整数相减可能超出 int。状态按下标存储,即使数值相同,只要选择的下标不同就会自然地分别计数。
C++ 实现¶
class Solution {
public:
int numberOfArithmeticSlices(std::vector<int>& nums) {
int n = static_cast<int>(nums.size());
std::vector<std::unordered_map<long long, long long>> dp(n);
long long answer = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
long long difference =
static_cast<long long>(nums[i]) - nums[j];
long long previous = 0;
auto it = dp[j].find(difference);
if (it != dp[j].end()) previous = it->second;
dp[i][difference] += previous + 1;
answer += previous;
}
}
return static_cast<int>(answer);
}
};
代码分析¶
每个 previous 状态追加当前元素后长度至少增加到 3,因此只把它加入答案;新增的二元组只作为未来延伸的中间状态,不会被误计入。状态按“结尾下标 + 公差”区分,覆盖了重复值和不同下标选择。共有 O(n^2) 个下标对,平均时间复杂度为 O(n^2),状态空间复杂度为 O(n^2)。