0446. Arithmetic Slices II - Subsequence ======================================== 题目信息 -------- :题号: 0446 :难度: Hard :主题: 子序列、等差数列、长度至少三、按下标计数 :原题: `LeetCode 0446 `_ :重点: 子序列不要求连续但必须保持下标顺序、相邻差值固定、不同下标选择分别计数 题目重述 -------- 给定整数数组 ``nums``,统计其中长度至少为 3 的等差子序列数量。子序列通过删除任意数量元素得到,保留元素的下标顺序不能改变,但它们在原数组中不必连续。 一个子序列是等差序列,当且仅当任意相邻两项的差值都相同。由不同下标集合形成的子序列需要分别计数,即使它们的数值序列完全相同。``nums.length`` 位于 ``[1, 1000]``,元素在 32 位有符号整数范围内,题目保证最终答案适合 32 位有符号整数。 自建示例 -------- 连续数组中存在三条等差子序列: .. code-block:: text 输入:nums = [1, 3, 5, 7] 输出:3 解释:合法子序列为 [1,3,5]、[3,5,7] 和 [1,3,5,7]。 重复值按下标组合计数: .. code-block:: text 输入: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++ 实现 -------- .. code-block:: cpp class Solution { public: int numberOfArithmeticSlices(std::vector& nums) { int n = static_cast(nums.size()); std::vector> 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(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(answer); } }; 代码分析 -------- 每个 ``previous`` 状态追加当前元素后长度至少增加到 3,因此只把它加入答案;新增的二元组只作为未来延伸的中间状态,不会被误计入。状态按“结尾下标 + 公差”区分,覆盖了重复值和不同下标选择。共有 ``O(n^2)`` 个下标对,平均时间复杂度为 ``O(n^2)``,状态空间复杂度为 ``O(n^2)``。