LeetCode 446. 等差数列划分 II - 子序列

2022-05-23 HGNULB 约 8 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 446. 等差数列划分 II - 子序列

题意分析

要统计数组中有多少个「等差子序列」。这里的子序列只要求下标严格递增、不要求连续，等差要求相邻两项之差恒定，且题目规定长度至少为 3 才算数。

统计的对象是下标组合而不是数值组合：两个内容完全相同但下标不同的子序列算作两个不同的答案。这一点决定了不能对数组去重，也不能因为数值重复而合并计数。

数组长度上限只有一千，这个规模明确指向平方级的算法——它允许枚举所有下标对，但不允许枚举所有子序列。

元素取值范围是 32 位整数的全域，两个元素相减可能超出 32 位表示范围，所以公差必须用 64 位存。这是本题最隐蔽的一个坑。

边界方面：数组长度小于 3 时答案为 0；全部元素相同时公差为 0 的等差子序列极多，答案可能相当大，但题目保证结果在 32 位范围内。

解法：按结尾和公差哈希 DP

核心思路

暴力做法是枚举所有子序列再验证，代价是 $2^n$，长度一千时完全不可行。往动态规划方向想，第一反应是用「以下标 $i$ 结尾的等差子序列个数」当状态，但这个定义立刻失效：要判断能否把 $nums[i]$ 接到某个子序列后面，必须知道那个子序列的公差是多少，而这个信息被状态丢掉了。

补上这一维就得到正确的状态定义：$dp[i][d]$ 表示以下标 $i$ 结尾、公差为 $d$、长度至少为 2 的子序列个数。注意这里刻意把门槛放宽到 2 而不是 3，原因马上就清楚了。

转移时枚举一个更小的下标 $j$，令 $d = nums[i] - nums[j]$。任何一个「以 $j$ 结尾、公差为 $d$、长度至少为 2」的子序列，接上 $nums[i]$ 之后长度至少变成 3，正好是一个合法答案；除此之外，$(j, i)$ 这一对本身也构成一个长度为 2 的新序列。于是转移写作：

$dp[i][d] \mathrel{+}= dp[j][d] + 1$

而答案的累加恰好是 $dp[j][d]$ 这一项——它统计的是「长度从至少 2 变成至少 3」的那些序列。也就是说，每一次转移中被继承过来的部分就是新产生的合法答案，而那个额外的 1 只进状态、不进答案。这就是把门槛定在 2 的意义：它让「长度至少 3」的计数在转移中自然浮现，不必再维护一维长度。

状态数量方面，$i$ 有 $n$ 种取值，公差取值稀疏且最多 $n$ 种（对固定的 $i$，不同的 $j$ 最多产生 $i$ 个不同公差），所以第二维用哈希表按需存储而不是开数组——公差的值域宽达 $2^{33}$，开数组是不可能的。

解题步骤

为每个下标准备一个空哈希表，键是公差、值是计数。用哈希表而非二维数组，是因为公差的取值范围极大但实际出现的数量很少，稀疏存储才是可行的。

外层从左到右枚举结尾下标 $i$，内层枚举所有 $j < i$。这个顺序保证了转移时 $dp[j]$ 已经完全计算好，符合动态规划「只依赖已确定状态」的要求。

计算公差时先把两个元素各自转成 64 位再相减。若在 32 位下相减，nums = [2147483647, -2147483648] 这类输入会溢出，两个本不相同的公差可能撞成同一个键。

取出 $dp[j][d]$，键不存在时视作 0。这个值直接累加进答案，因为它代表的每一个长度至少为 2 的序列，接上 $nums[i]$ 后都变成了一个长度至少为 3 的合法子序列。

把 $dp[j][d] + 1$ 累加到 $dp[i][d]$ 上。必须是累加而不是赋值，因为不同的 $j$ 可能给出相同的公差，它们的贡献要叠加。那个 1 代表 $(j, i)$ 这个新的二元序列。

答案变量用 64 位累加、最后再转回 32 位，避免中间过程溢出。

以 nums = [2, 4, 6, 8, 10] 走一遍：所有哈希表初始为空，答案为 0。

$i = 1$（值 4）：$j = 0$ 时公差为 2，$dp[0][2]$ 不存在记作 0，答案不变；$dp[1][2] = 0 + 0 + 1 = 1$，对应序列 $(2, 4)$。

$i = 2$（值 6）：$j = 0$ 时公差 4，继承值 0，$dp[2][4] = 1$。$j = 1$ 时公差 2，$dp[1][2] = 1$，答案加 1 变成 1（新答案是 $(2, 4, 6)$）；$dp[2][2] = 1 + 1 = 2$，对应 $(2,4,6)$ 与 $(4,6)$。

$i = 3$（值 8）：$j = 0$ 公差 6，$dp[3][6] = 1$。$j = 1$ 公差 4，$dp[1][4]$ 为 0，$dp[3][4] = 1$。$j = 2$ 公差 2，$dp[2][2] = 2$，答案加 2 变成 3（新增 $(2,4,6,8)$ 与 $(4,6,8)$）；$dp[3][2] = 2 + 1 = 3$。

$i = 4$（值 10）：$j = 0$ 公差 8，$dp[4][8] = 1$。$j = 1$ 公差 6，继承 0，$dp[4][6] = 1$。$j = 2$ 公差 4，$dp[2][4] = 1$，答案加 1 变成 4（新增 $(2,6,10)$）；$dp[4][4] = 1 + 1 = 2$。$j = 3$ 公差 2，$dp[3][2] = 3$，答案加 3 变成 7（新增 $(2,4,6,8,10)$、$(4,6,8,10)$、$(6,8,10)$）；$dp[4][2] = 3 + 1 = 4$。

最终答案 7。逐一列举验证：公差为 2 的有 $(2,4,6)$、$(4,6,8)$、$(6,8,10)$、$(2,4,6,8)$、$(4,6,8,10)$、$(2,4,6,8,10)$ 共六个，公差为 4 的有 $(2,6,10)$ 一个，合计正是 7 个。

代码实现

class Solution {
    // dp[i][diff] 表示以 nums[i] 结尾、公差为 diff、长度至少为 2 的子序列数量。
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        List<Map<Long, Integer>> dp = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            dp.add(new HashMap<>());
        }

        long answer = 0;
        for (int i = 0; i < n; i++) {
            Map<Long, Integer> cur = dp.get(i);
            for (int j = 0; j < i; j++) {
                long diff = (long) nums[i] - nums[j];
                int count = dp.get(j).getOrDefault(diff, 0);
                answer += count;
                cur.put(diff, cur.getOrDefault(diff, 0) + count + 1);
            }
        }

        return (int) answer;
    }
}

func numberOfArithmeticSlices(nums []int) int {
    // dp[i][diff] 表示以 nums[i] 结尾、公差为 diff、长度至少为 2 的子序列数量。
    n := len(nums)
    dp := make([]map[int64]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make(map[int64]int)
    }

    res := 0
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            diff := int64(nums[i]) - int64(nums[j])
            count := dp[j][diff]
            res += count
            dp[i][diff] = dp[i][diff] + count + 1
        }
    }

    return res
}

复杂度分析

时间复杂度：$O(n^2)$，外层枚举结尾下标、内层枚举更小的下标，共 $n^2 / 2$ 对，每对只做常数次哈希查询与写入。

空间复杂度：$O(n^2)$，第 $i$ 个哈希表最多存 $i$ 个不同公差，全部相加是平方级；无法降到线性，因为每个结尾位置的公差分布互不相同。

关键点总结

状态定义不足时先问「转移需要哪些信息」。这里判断能否接续必须知道公差，于是公差自然成为状态的一维，这是所有子序列类动态规划的通用推导方式。

值域巨大而实际取值稀疏时，用哈希表代替数组做状态的某一维。公差跨度达 $2^{33}$，只有稀疏存储可行。

把长度门槛故意放宽一格（存「至少 2」而不是「至少 3」），让答案在转移的继承项里自然浮现，是一个能省掉一整维状态的常用技巧。

转移必须是累加而非赋值。同一个结尾位置可以从多个前驱得到相同公差，漏掉叠加会大幅少算。

相减前先扩展到 64 位。凡是元素取值覆盖 32 位全域又要做差的题，这一步都是必须的。

面试视角：先说清朴素状态为什么不够用，再给出二维定义，最后解释「继承项即答案」的道理——这三步讲完，代码本身只有十行。若被追问空间能否优化，答「不能显著优化，因为每个下标的公差分布本质上互不相同」比硬凑一个错误方案更好。

易错点总结

错误写法：用 32 位整数计算公差。nums = [2147483647, -2147483648, ...] → 相减溢出，得到的公差与另一对下标的公差意外相等，计数被错误合并。

错误写法：把 $dp[j][d] + 1$ 整体累加进答案。nums = [2, 4, 6] → 答案变成 2，把长度为 2 的 $(4, 6)$ 也算作合法结果，正确答案是 1。

错误写法：转移写成赋值 dp[i][d] = dp[j][d] + 1。nums = [1, 3, 5, 3, 5] 这类同一公差有多个前驱的用例 → 后一个 $j$ 覆盖了前一个 $j$ 的贡献，结果偏小。

错误写法：状态只按公差不按结尾下标，用一个全局哈希表统计。nums = [2, 4, 6, 8] → 不同结尾位置的计数混在一起，会把下标不递增的组合也算进去，结果偏大。

错误写法：为了「去重」先把数组排序或去掉重复元素。nums = [3, 3, 3, 3] → 去重后答案为 0，而正确答案是 4（四个 3 中任取 3 个共 4 种下标组合）。

错误写法：认为公差为 0 的情况需要特判或排除。nums = [0, 0, 0] → 会返回 0，但 $(0, 0, 0)$ 是合法的等差子序列，正确答案是 1。

错误写法：内层循环写成 $j > i$ 或双向枚举。任意用例 → 子序列的下标不再严格递增，同一组合被统计两次甚至更多。

错误写法：答案变量用 32 位累加。全部元素相同且长度接近上限的用例 → 中间累加过程溢出成负数，即使最终结果在 32 位内也会输出错值。

错误写法：取 $dp[j][d]$ 时不处理键不存在的情况，直接解引用。首次出现的公差 → 在 Java 里抛出空指针异常，或在其他语言里读到未定义值。

相似题目

题目	难度	考察点
413. 等差数列划分	中等	要求连续子数组，状态退化成一维且可滚动优化
1027. 最长等差数列	中等	同样的二维状态，但值取长度的最大值而非方案计数
1218. 最长定差子序列	中等	公差已给定，状态降到一维，可线性时间完成
873. 最长的斐波那契子序列的长度	中等	状态改为记录最后两项，靠数值反查下标完成转移