等差数列划分 图解题解

等差数列划分这道题到底在数什么

给整数数组 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 长起。

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 ans

C++

#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;
    }
}