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

约 5 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 美团 百度
标签
数组 动态规划

题目描述

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

image-20260928224148135

image-20260928224148136

题意分析

统计所有长度至少为 3 的等差子序列。选择的下标必须递增，但可以跳过元素；只要下标组合不同，就算不同子序列，即使对应数值完全相同也要分别计数。

公差可以为正、负或零。题目保证最终答案可用 32 位整数表示，但两个元素的差可能超出这个范围，因此公差要使用 64 位整数。

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

核心思路

[!blue]

要给一个等差子序列追加新元素，需要知道它的最后一个位置和公差。定义 dp[i][d] 为“以下标 i 结尾、公差为 d、长度至少为 2”的子序列数量。状态刻意包含长度为 2 的序列，因为它们是以后组成合法三项序列的起点。

按最后两个下标 j < i 枚举，公差只能是 d = nums[i] - nums[j]。设 count = dp[j][d]，其中每个序列都能追加 nums[i]，并仍然保持公差 d。追加后长度至少为 3，所以这 count 个新序列既加入 dp[i][d]，也加入最终答案。

此外，单独选择 j、i 就组成一个新的二项序列，只能作为后续扩展的状态，当前还不能计入答案。因此转移是 dp[i][d] += count + 1，而答案只增加 count。

不同前驱 j 对应不同的倒数第二个下标，扩展出的序列不会重复；同一个前驱中不同的下标组合也会在追加后保持不同。每个合法序列都在处理其最后一个下标时被计入一次，因此这项累加既完整也不重计。

解题步骤

  1. 为每个结尾下标建立一张空哈希表，未出现过的公差计数视为 0。
  2. 从左到右枚举末项下标 i，再枚举全部 j < i，保证前驱状态已经计算完毕。
  3. 先把元素转换为宽整数，再计算公差 diff，读取 count = dp[j][diff]。
  4. 将 count 加入答案，并把 count + 1 累加到 dp[i][diff]。
  5. 返回答案。元素不足三个时，只会建立二项状态，不会给答案增加任何合法序列。

代码实现

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)$，枚举全部前后下标对。
  • 空间复杂度：$O(n^2)$，各结尾的不同公差状态总数至多平方级。

关键点总结

[!green]

  • 状态包含长度为 2 的序列，答案只统计长度至少为 3 的序列，两者范围不同。
  • +1 是新建二项序列，继承的 count 才是已经达到题目长度要求的新答案。
  • 同一结尾、同一公差可以由多个前驱产生，必须累加方案数。
  • 以最后两个下标划分来源，让每个合法序列都有唯一的计数时刻。

易错点总结

[!yellow]

  • 把 count + 1 全部加入答案，会把长度为 2 的序列错误算入。
  • 先排序或去重都会改变下标顺序或丢失不同选择，不能为了处理公差而修改原数组。
  • 只保存全局公差计数会丢失结尾位置，无法判断哪些序列可以向当前下标扩展。
  • 公差要先扩大操作数类型再相减；差值已经溢出后再转成宽整数，无法恢复原值。

相似题目

题目 难度 关联与区别
413. 等差数列划分 中等 连续区间只需比较相邻差值，本题允许跳过元素，需要为每个末项保存各公差的方案数。
1027. 最长等差数列 中等 同样按末项和公差建立状态，原题取最长长度，本题累加所有长度至少3的方案。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/18286390
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！