等差数列划分 图解题解
这道题到底在问什么
- 输入
- nums=[1,2,3,4]
- 输出
- 3([1,2,3]、[2,3,4]、[1,2,3,4])
- 输入
- nums=[1,3,5,7,9]
- 输出
- 6(整段等差,各长度子段共 6 个)
最优解：一步一步想明白
- 3记住「同公差就 cur+1 并 ans+=cur,断了就 cur 归 0」,下面每一帧都在套它。
- 4开局:前两个数还凑不成长度 3 的子段,cur=0、ans=0。从下标 2 起,每一步看 nums[i] 与前两个数是否构成等差。
- 5看下标 2(值 3):它和前一个的差是 1,前两个之间的差是 1。两差相等,公差延续。
- 6公差延续:cur 加到 1(以 3 结尾,新增了 1 个等差子段),ans 累加到 1。绿色是当前这条等差段。
- 7这里只新增了 1 个长度 3 的段 [1, 2, 3](高亮),它给 ans 贡献 +1。
- 8看下标 3(值 4):它和前一个的差是 1,前两个之间的差是 1。两差相等,公差延续。
- 9公差延续:cur 加到 2(以 4 结尾,新增了 2 个等差子段),ans 累加到 3。绿色是当前这条等差段。
- 10这 2 个新段里最短的是 [2, 3, 4](高亮),另一个更长的是 [1, 2, 3, 4],都是把它向左延伸而来;它们正好凑成这一步给 ans 的 +2。
- 11看下标 4(值 5):它和前一个的差是 1,前两个之间的差是 1。两差相等,公差延续。
- 12公差延续:cur 加到 3(以 5 结尾,新增了 3 个等差子段),ans 累加到 6。绿色是当前这条等差段。
- 13这 3 个新段里最短的是 [3, 4, 5](高亮),更长的 2 个是 [2, 3, 4, 5]、[1, 2, 3, 4, 5],都是把它向左延伸而来;它们正好凑成这一步给 ans 的 +3。
- 14看下标 5(值 9):它和前一个的差是 4,前两个之间的差是 1。两差不等,等差在这里断了。
- 15公差中断:cur 归 0,ans 保持 6 不变。注意不是从单个 9 重新开始,而是继续往后扫,用最近相邻的两个数当候选,看下一步的差能否重新连成等差段。
- 16看下标 6(值 8):它和前一个的差是 -1,前两个之间的差是 4。两差不等,等差在这里断了。
- 17公差中断:cur 归 0,ans 保持 6 不变。注意不是从单个 8 重新开始,而是继续往后扫,用最近相邻的两个数当候选,看下一步的差能否重新连成等差段。
- 18看下标 7(值 7):它和前一个的差是 -1,前两个之间的差是 -1。两差相等,公差延续。
- 19公差延续:cur 加到 1(以 7 结尾,新增了 1 个等差子段),ans 累加到 7。绿色是当前这条等差段。
- 20这里只新增了 1 个长度 3 的段 [9, 8, 7](高亮),它给 ans 贡献 +1。
- 21看下标 8(值 6):它和前一个的差是 -1,前两个之间的差是 -1。两差相等,公差延续。
- 22公差延续:cur 加到 2(以 6 结尾,新增了 2 个等差子段),ans 累加到 9。绿色是当前这条等差段。
- 23这 2 个新段里最短的是 [8, 7, 6](高亮),另一个更长的是 [9, 8, 7, 6],都是把它向左延伸而来;它们正好凑成这一步给 ans 的 +2。
- 24扫完整个数组,ans = 9。其中开头 [1,2,3,4,5] 贡献 6 个、结尾 [9,8,7,6] 贡献 3 个,中间断开不贡献,合计 9。
⚠️ 容易写错的地方
✗ 错：同公差时只给 ans 加 1
✓ 对：ans 要加 cur(累加当前段数)
多接一个同公差元素,会新增「以它结尾」的多个等差段(长度 3、4、…),个数正好是 cur;只加 1 会漏数较长的子段
✗ 错：断点时忘了把 cur 归 0
✓ 对：差不相等就 cur = 0
cur 是「以当前位置结尾的连续等差段数」,一旦断开,之前的段都不能延续,必须清零重新计
✗ 错：从下标 0 或 1 开始判断
✓ 对：从下标 2 起(才有三个数)
等差子段至少长 3,需要 nums[i]、nums[i−1]、nums[i−2] 三个数才能比较两个差
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
cur = ans = 0
for i in range(2, len(nums)):
if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
cur += 1
ans += cur
else:
cur = 0
return ansC++
#include <vector>
using namespace std;
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int cur = 0, ans = 0;
for (int i = 2; i < (int)nums.size(); ++i) {
if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) ans += ++cur;
else cur = 0;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int cur = 0, ans = 0;
for (int i = 2; i < nums.length; i++) {
if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) ans += ++cur;
else cur = 0;
}
return ans;
}
}复杂度
时间
O(n)
n 是数组长度。只从下标 2 扫到末尾一遍,每步常数操作
空间
O(1)
只用 cur、ans 两个变量,不开额外数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 等差数列划分 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能用一个 dp 数组 dp[i] 表示以 i 结尾的等差段数,而不是滚动变量?+
可以。dp[i] = (若 nums[i]−nums[i−1]==nums[i−1]−nums[i−2]) 则 dp[i−1]+1,否则 0;答案是所有 dp[i] 之和。这就是本题 DP 的完整形态。观察到 dp[i] 只依赖 dp[i−1],于是把数组压成一个滚动变量 cur,空间从 O(n) 降到 O(1),也就是代码里的写法。
如果改成统计「长度恰好为 k」的等差子数组个数呢?+
思路相近但需调整累加规则。维护当前连续等差 run 的元素长度 len:初始化和断开时都把 len 重置为 2(当前相邻两数自成新候选段),同公差则 len+1。每到一个位置,当 len ≥ k 时,以当前位置结尾、长度恰为 k 的等差子段有 1 个(从当前往左数 k 个),答案 +1。本题是「长度 ≥ 3 的全部」,所以用 cur 累加所有长度;固定长度 k 则每步至多 +1。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 等差数列划分 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。