题目描述
思路解析动画文字版
记住「同公差就 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 474 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题