题目描述
思路解析
一句话答案：LeetCode 413 等差数列划分：数长度≥3 的连续等差子数组个数。dp[i] 记以 i 结尾的等差子段数，同公差就 dp[i]=dp[i-1]+1，否则 0，答案累加所有 dp[i]，一遍扫描 O(n) 时间、O(1) 空间。
等差数列划分这道题到底在数什么
给整数数组 nums，数出长度至少 3 的连续子数组里有多少段是等差数列（相邻两项的差处处相等）。要的是段数，不是逐一列出。nums=[1,2,3,4] 有 3 段：1,2,3、2,3,4、1,2,3,4。
为什么把所有连续子数组都查一遍会太慢
枚举每个连续子数组再核对是不是等差：长度 n 约有 n 平方除以 2 个子数组，边扫边判也要 O(n 平方)，且重复劳动明显——核对以某位置结尾的长段时，它前面那截短段刚被核对过。这种「短段被长段重算」正是递推能省的地方；递推即拿前面算好的结果推出当前值。
dp[i] 定成以 i 结尾的等差段数
不数所有子数组，只盯结尾。定义 dp[i] 为「以 nums[i] 结尾的等差连续子段有几个」，这样每段等差子数组都有唯一结尾下标，所有 dp[i] 相加就不重不漏数完全部段。能否延续只看最近三数：若 nums[i] 减 nums[i-1] 等于 nums[i-1] 减 nums[i-2]，公差（相邻两数的差）接上、dp[i] 有值，否则断开、dp[i]=0。要三个数才能比两个差，故从下标 2 起判。
同公差时为什么是 dp[i-1]+1 而不是从头数
公差延续时 dp[i]=dp[i-1]+1。把「以 i 结尾的等差段」拆成两拨。第一拨是所有以 i-1 结尾的等差段各自向右接上 nums[i]：末尾添个同公差的数仍是等差，只是结尾从 i-1 挪到 i，恰好 dp[i-1] 个。第二拨是一个全新最短段 nums[i-2]、nums[i-1]、nums[i]。合起来 dp[i-1]+1，没有第三种——dp[i-1] 早把结尾在 i-1 的段数清了，拿来延伸即可，不必从头重数。
每算一格把 dp[i] 累加进答案即总段数；同公差加的是 dp[i] 不是 1，因一次延伸新增好几段。
拿 [1,3,5,7,9] 把 dp 一格格填出来
从下标 2 起。值 5：5 减 3 和 3 减 1 都是 2，dp[2]=dp[1]+1=0+1=1，答案 1，新段 1,3,5。值 7：差都 2，dp[3]=dp[2]+1=2，答案 1+2=3，这 2 段是 1,3,5 延伸成 1,3,5,7 加新段 3,5,7。值 9：差都 2，dp[4]=dp[3]+1=3，答案 3+3=6，3 段是延伸的 1,3,5,7,9、3,5,7,9 加新段 5,7,9。dp 依次 1、2、3，答案 6，对上题面：dp 值本身每步只涨 1（1、2、3），把这三个 dp 值累加才凑成答案 6。
复杂度多少，不足 3 个和断点归零别写错
只从下标 2 扫到末尾一遍，每步一次比较加常数次加法，时间 O(n)；dp[i] 只用 dp[i-1]，压成一个滚动变量 cur 即可（只留最近一项、循环覆盖旧值），空间 O(1)。
两处边界。一是不足 3 个数：长度小于 3 时凑不出段，答案 0，循环从下标 2 起天然进不去。二是断点后别把 cur 写反：公差一断 cur 必须归 0，因为以当前位置结尾的段全断了、都延续不了；此时不从单个数从头起，而是往后扫、拿最近两数当候选，下个差对上再从 1 长起。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「同公差就 cur+1 并 ans+=cur,断了就 cur 归 0」,下面每一帧都在套它。
开局:前两个数还凑不成长度 3 的子段,cur=0、ans=0。从下标 2 起,每一步看 nums[i] 与前两个数是否构成等差。
看下标 2(值 3):它和前一个的差是 1,前两个之间的差是 1。两差相等,公差延续。
公差延续:cur 加到 1(以 3 结尾,新增了 1 个等差子段),ans 累加到 1。绿色是当前这条等差段。
这里只新增了 1 个长度 3 的段 [1, 2, 3](高亮),它给 ans 贡献 +1。
看下标 3(值 4):它和前一个的差是 1,前两个之间的差是 1。两差相等,公差延续。
公差延续:cur 加到 2(以 4 结尾,新增了 2 个等差子段),ans 累加到 3。绿色是当前这条等差段。
这 2 个新段里最短的是 [2, 3, 4](高亮),另一个更长的是 [1, 2, 3, 4],都是把它向左延伸而来;它们正好凑成这一步给 ans 的 +2。
看下标 4(值 5):它和前一个的差是 1,前两个之间的差是 1。两差相等,公差延续。
公差延续:cur 加到 3(以 5 结尾,新增了 3 个等差子段),ans 累加到 6。绿色是当前这条等差段。
这 3 个新段里最短的是 [3, 4, 5](高亮),更长的 2 个是 [2, 3, 4, 5]、[1, 2, 3, 4, 5],都是把它向左延伸而来;它们正好凑成这一步给 ans 的 +3。
看下标 5(值 9):它和前一个的差是 4,前两个之间的差是 1。两差不等,等差在这里断了。
公差中断:cur 归 0,ans 保持 6 不变。注意不是从单个 9 重新开始,而是继续往后扫,用最近相邻的两个数当候选,看下一步的差能否重新连成等差段。
看下标 6(值 8):它和前一个的差是 -1,前两个之间的差是 4。两差不等,等差在这里断了。
公差中断:cur 归 0,ans 保持 6 不变。注意不是从单个 8 重新开始,而是继续往后扫,用最近相邻的两个数当候选,看下一步的差能否重新连成等差段。
看下标 7(值 7):它和前一个的差是 -1,前两个之间的差是 -1。两差相等,公差延续。
公差延续:cur 加到 1(以 7 结尾,新增了 1 个等差子段),ans 累加到 7。绿色是当前这条等差段。
这里只新增了 1 个长度 3 的段 [9, 8, 7](高亮),它给 ans 贡献 +1。
看下标 8(值 6):它和前一个的差是 -1,前两个之间的差是 -1。两差相等,公差延续。
公差延续:cur 加到 2(以 6 结尾,新增了 2 个等差子段),ans 累加到 9。绿色是当前这条等差段。
这 2 个新段里最短的是 [8, 7, 6](高亮),另一个更长的是 [9, 8, 7, 6],都是把它向左延伸而来;它们正好凑成这一步给 ans 的 +2。
扫完整个数组,ans = 9。其中开头 [1,2,3,4,5] 贡献 6 个、结尾 [9,8,7,6] 贡献 3 个,中间断开不贡献,合计 9。
边界:不足 3 个为 0;整段等差累加增长;全相等公差 0 也算。
两个延伸:dp[i] 可滚动压成 O(1);统计定长 k 需改累加规则。
参考代码
from typing import Listclass 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 ans复杂度
- 时间：O(n)，n 是数组长度。只从下标 2 扫到末尾一遍,每步常数操作
- 空间：O(1)，只用 cur、ans 两个变量,不开额外数组
易错点
面试追问把动画讲成自己的话
追问能不能用一个 dp 数组 dp[i] 表示以 i 结尾的等差段数,而不是滚动变量?
追问如果改成统计「长度恰好为 k」的等差子数组个数呢?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
环绕字符串中唯一的子字符串
LeetCode 467 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题