LeetCode 413. 等差数列划分

2022-05-27 HGNULB 约 8 分钟

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

分类

题目描述

✅ 413. 等差数列划分

题意分析

要数的是一个整数数组里有多少个「连续」的子数组满足两个条件：长度至少为 $3$，且相邻两项之差处处相同。注意统计对象是子数组不是子序列，元素必须在原数组中挨在一起，这个「连续」的限定是全题最重要的信号。

长度至少为 $3$ 这一条也值得留意：它排除了长度为 $2$ 的片段——任意两个数都能构成一个公差，如果允许长度 $2$，答案会退化成一个平凡的组合数。

边界情况有几处。数组长度小于 $3$ 时不可能存在合法片段，答案为 $0$。公差允许为 $0$，也就是说 [7,7,7] 是合法的等差数列。元素可能为负、公差也可能为负，比较时不能对差值取绝对值。数据范围给到 $-1000 \le \text{nums}[i] \le 1000$，相邻差值不会溢出，但答案本身可能达到 $O(n^2)$ 量级，在 $n \le 5000$ 时仍在 int 范围内。

解法：线性 DP 计数

核心思路

最朴素的做法是枚举所有子数组的左右端点，再逐个验证是否等差，那是 $O(n^3)$；稍作优化，固定左端点向右扩展并维护公差，可以做到 $O(n^2)$。瓶颈在于同一段等差区间被反复验证了很多遍——一个长度为 $k$ 的极大等差段，内部所有子段都被独立检查了一次。

换个统计口径能避开这种重复。与其枚举左右端点，不如按「右端点」分类计数：把所有合法片段按它的最后一个下标分组，只要能对每个下标 $i$ 求出「以 $i$ 结尾的合法片段有几个」，全部相加就是答案。这个换口径的动作是把 $O(n^2)$ 降到 $O(n)$ 的关键。

于是定义状态 $dp[i]$ 表示以下标 $i$ 为最后一个元素的等差子数组个数（长度至少 $3$）。转移的依据是一个简单的观察：若 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，那么每一个以 $i-1$ 结尾的合法片段，末尾接上 nums[i] 后仍然合法，这贡献了 $dp[i-1]$ 个；此外还新增了恰好由 nums[i-2]、nums[i-1]、nums[i] 三个元素构成的那一个片段。因此 $dp[i] = dp[i-1] + 1$。反之，若这三项不构成等差，则任何以 $i$ 结尾的片段都会在最后三项处断裂，$dp[i] = 0$。

答案是 $\sum_i dp[i]$。由于转移只依赖前一项，$dp$ 数组可以压成一个滚动变量 cur，空间降到常数。

解题步骤

先判长度：数组元素少于 $3$ 个时直接返回 $0$。这既是题意要求，也避免了后续访问 nums[i-2] 时下标为负。

准备两个变量，total 累计答案，cur 表示滚动的 $dp$ 值。两者都初始化为 $0$，因为在还没扫到任何三元组之前，既没有合法片段也没有可延长的片段。

从下标 $2$ 开始向右遍历。之所以从 $2$ 起步，是因为判定一个位置能否作为等差片段的末尾，至少需要它前面还有两个元素。

对每个 $i$ 比较 nums[i] - nums[i-1] 与 nums[i-1] - nums[i-2]。用两个差值直接相等来判断，而不是先算出公差再比对，这样既省去了「当前公差」这个额外状态，也天然处理了公差为 $0$ 和公差为负的情况。

若相等，执行 cur++ 再 total += cur。先自增再累加对应的是 $dp[i] = dp[i-1] + 1$ 与 $\text{total} \mathrel{+}= dp[i]$ 两步，顺序反了就会漏掉当前位置新产生的那个长度为 $3$ 的片段。

若不相等，把 cur 置为 $0$。这一步是断点重置：等差性一旦在 $i$ 处断裂，之前积累的所有片段都无法延长到 $i$，必须清零而不是保留。

遍历结束返回 total。

以 [1,2,3,4,6,7,8] 走一遍：初始 total = 0、cur = 0。$i = 2$ 时，nums[2] - nums[1] = 3 - 2 = 1，nums[1] - nums[0] = 2 - 1 = 1，两者相等，cur 变为 $1$，total 变为 $1$，对应新片段 [1,2,3]。$i = 3$ 时，4 - 3 = 1 等于 3 - 2 = 1，cur 变为 $2$，total 变为 $3$，新增的两个片段是 [2,3,4] 和 [1,2,3,4]。$i = 4$ 时，6 - 4 = 2 不等于 4 - 3 = 1，等差性断裂，cur 重置为 $0$，total 保持 $3$。$i = 5$ 时，7 - 6 = 1 不等于 6 - 4 = 2，仍不成立，cur 保持 $0$，total 保持 $3$。$i = 6$ 时，8 - 7 = 1 等于 7 - 6 = 1，cur 变为 $1$，total 变为 $4$，新片段是 [6,7,8]。遍历结束返回 $4$。手工枚举验证：[1,2,3]、[2,3,4]、[1,2,3,4]、[6,7,8] 恰好四个，结果一致。

代码实现

// 否则 dp[i] = 0。
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) {
            return 0;
        }

        int total = 0;
        int cur = 0;

        for (int i = 2; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                cur++;
                total += cur;
            } else {
                cur = 0;
            }
        }

        return total;
    }
}

// 否则 dp[i] = 0。
func numberOfArithmeticSlices(nums []int) int {
    if len(nums) < 3 {
        return 0
    }

    total := 0
    cur := 0

    for i := 2; i < len(nums); i++ {
        if nums[i]-nums[i-1] == nums[i-1]-nums[i-2] {
            cur++
            total += cur
        } else {
            cur = 0
        }
    }

    return total
}

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组长度。下标从 $2$ 扫到 $n-1$ 共 $n-2$ 轮，每轮只做两次减法、一次比较和常数次赋值，没有任何嵌套或回溯。

空间复杂度：$O(1)$。由于 $dp[i]$ 只依赖 $dp[i-1]$，整张 $dp$ 表被压缩成单个变量 cur，另外只有一个累加器 total，与输入规模无关。

关键点总结

计数类问题卡在重复统计时，优先尝试「按右端点分组」这一换口径的手法。把「有多少个合法区间」拆成「以每个位置结尾的合法区间有多少个」，往往能把平方级枚举变成线性递推。

状态定义必须显式包含「以 $i$ 结尾」这个限定。若把 $dp[i]$ 定义成「前 $i$ 项中的片段总数」，转移时就无法知道能延长多少，递推关系反而写不出来。

递推式 $dp[i] = dp[i-1] + 1$ 中的 $+1$ 有明确含义——新增的那个恰好三元的片段；$dp[i-1]$ 则对应所有旧片段的整体延长。能把这两部分说清楚，才算真正理解而非背公式。

转移只依赖相邻一项时，$dp$ 数组应当立刻降维成滚动变量。这是线性 DP 最常见也最容易被忽略的优化。

面试视角：面试官通常会先看你能否写出 $O(n^2)$ 的枚举，再问「能不能做到线性」。主动说出「换成按右端点计数」这句话，是这题最想听到的答案。

面试视角：追问往往落在「如果改成子序列而非子数组呢」。此时状态要扩展成「以 $i$ 结尾、公差为 $d$」的二维哈希形式，能顺口说出这个演化方向会显著加分。

易错点总结

错误写法：total += cur 写在 cur++ 之前 → 对 [1,2,3] 会先把旧值 $0$ 累加进 total，返回 $0$，而正确答案是 $1$。

错误写法：不等差时忘记把 cur 置零 → 对 [1,2,3,8,9,10]，在下标 $3$ 处断裂后 cur 仍是 $1$，下标 $5$ 处会算成 $2$，最终返回 $3$，正确答案是 $2$。

错误写法：循环从下标 $0$ 或 $1$ 开始 → 访问 nums[i-2] 时下标为负，直接数组越界崩溃。

错误写法：数组长度小于 $3$ 时不特判 → Java 侧循环恰好不执行还能返回 $0$，但若实现中提前访问了 nums[2] 做初始化，对 [1] 这类输入会越界。

错误写法：判断等差时先算 d = nums[1] - nums[0] 并全程复用这个公差 → 对 [1,3,5,6,7,8] 会把公差锁死为 $2$，后半段公差为 $1$ 的 [5,6,7]、[6,7,8]、[5,6,7,8] 全被漏掉，返回 $1$ 而正确答案是 $4$。公差必须随位置动态判定。

错误写法：用 Math.abs(nums[i] - nums[i-1]) == Math.abs(nums[i-1] - nums[i-2]) 判断 → 对 [1,2,1] 两个差值的绝对值都是 $1$，会被误判为等差并计入答案，但它显然不是等差数列。

错误写法：认为公差为 $0$ 不算等差而额外排除 → 对 [7,7,7,7] 会返回 $0$，正确答案是 $3$。

错误写法：把 cur 理解成「当前等差段的长度」并直接累加 → 对 [1,2,3,4] 会累加成 $3 + 4 = 7$，正确答案是 $3$；cur 表示的是以当前位置结尾的片段个数，等于当前极大等差段长度减 $2$。

错误写法：改用枚举左右端点的写法但内层不提前跳出 → 对全等差的 $n = 5000$ 输入会退化成 $O(n^2)$ 甚至 $O(n^3)$，在大数据下超时。

错误写法：把统计口径当成「极大等差段的个数」 → 对 [1,2,3,4] 只会返回 $1$，但题目要数的是所有子数组，正确答案是 $3$。

相似题目

题目	难度	考察点
446. 等差数列划分 II - 子序列	困难	元素不必相邻，状态要扩成「以 $i$ 结尾、公差为 $d$」的哈希表
1027. 最长等差数列	中等	求最长而非计数，同样需要把公差编进状态维度
1218. 最长定差子序列	中等	公差已给定，可用值到长度的哈希表做 $O(n)$ 递推
674. 最长连续递增序列	简单	同样是断点重置的线性扫描，但维护的是长度而非片段数
53. 最大子数组和	中等	同为「以 $i$ 结尾」的滚动状态，转移改为在延长与重启间取较大值