LeetCode 413. 等差数列划分
题目描述
题意分析
统计长度至少为 3、相邻元素差值相同的连续子数组数量。不同起点或终点都算不同子数组，即使它们属于同一个较长等差段，也要分别计数；公差可以为 0 或负数。
解法：线性 DP 计数
核心思路
[!blue]
枚举每个子数组会重复检查很多差值。可以按右端点分组，用
cur记录恰好以当前位置结尾的合法子数组数量，用total累加已经处理过的右端点贡献。处理下标
i时，比较nums[i] - nums[i - 1]和nums[i - 1] - nums[i - 2]。若两者相等，原先以i - 1结尾的每个等差子数组都可以追加nums[i]，这些延长后的长度至少为 4；此外，末尾三个元素还新组成一个长度为 3 的等差子数组。因此新贡献为cur + 1。这个分类没有遗漏：以
i结尾的合法子数组，要么恰好长 3，要么去掉最后一个元素后属于上一轮计数。两类长度不同，也不会重复。若末尾两个差值不同，连最后三个元素都不等差，更长的子数组也必然包含这处断裂，所以当前贡献必须归零。每个子数组只有一个右端点，把每轮的
cur加入total就能恰好统计全部答案。只需要上一轮的贡献，因此无需保存整张 DP 数组。
解题步骤
- 数组长度小于 3 时直接返回 0，否则初始化
cur = 0、total = 0。- 从下标 2 开始比较末尾两个差值。
- 差值相同则先令
cur加一，再把它加入total。- 差值不同则把
cur清零，但保留已有的total。- 遍历结束后返回
total。
代码实现
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;
}
}
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)$，每个末端一次判断。
- 空间复杂度：$O(1)$，当前贡献与累计总数。
关键点总结
[!green]
- 当前变量是片段数量，不是等差段长度。
- 差值保留符号，正一与负一不是相同公差。
- 按右端点累加贡献，每个合法子数组既不会漏掉，也不会被算两次。
易错点总结
[!yellow]
- 先累加再自增，会漏掉新出现的三项片段。
- 断裂不清零，会把不同等差段连在一起。
- 对差取绝对值，会把上升与下降的变化误认为相同公差。
- 断裂时不能清空
total，此前结束的合法子数组仍然有效。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 446. 等差数列划分 II - 子序列 | 困难 | 本题要求连续区间，原题允许跳过元素形成子序列，需要按末项和公差累计状态。 |
| 1027. 最长等差数列 | 中等 | 同样围绕公差延续，原题求最长等差子序列，本题统计连续等差区间总数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！