动态规划 等差数列划分
413. 等差数列划分
问题描述
给你一个整数数组 nums，返回数组中所有等差数列子数组的个数。
一个等差数列子数组是指长度至少为 3 的连续子数组，且元素之间的差值恒定（即 nums[i+1] - nums[i] == d 对所有 i 成立）。
示例：
示例 1：输入：nums = [1,2,3,4]输出：3解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。示例 2：输入：nums = [1]输出：0算法思路
核心：
- 一旦发现一段长度为
L ≥ 3的等差序列，它内部包含的等差子数组数量是可计算的。 - 例如：长度为
n的等差序列中，长度 ≥3 的连续子数组个数为：
(n−2)+(n−3)+⋯+1=(n−2)(n−1)2(n-2) + (n-3) + \\dots + 1 = \\frac{(n-2)(n-1)}{2}(n−2)+(n−3)+⋯+1=2(n−2)(n−1)
这不是最优解法。
更优思路：动态规划（DP）
定义 dp[i] 表示以 nums[i] 结尾的、且是某个等差数列一部分的“新增”等差子数组个数。
- 如果
nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，说明可以延续前面的等差趋势。 - 那么以
i结尾的等差子数组个数比以i-1结尾的多一个（因为可以在每个原有子数组后加当前元素，并新增[i-2,i-1,i]）。 - 所以：
dp[i] = dp[i-1] + 1 - 否则：
dp[i] = 0
最终答案就是所有 dp[i] 的和。
关键：
dp[i]不是“最长长度”，而是“新增的等差子数组数量”。
代码实现
class Solution { /** * 计算数组中所有等差数列子数组的个数 * * @param nums 整数数组 * @return 等差数列子数组的总数 */ public int numberOfArithmeticSlices(int[] nums) { // 边界检查：长度小于3无法构成等差数列 if (nums == null || nums.length < 3) { return 0; } int n = nums.length; int[] dp = new int[n]; // dp[i] 表示以 nums[i] 结尾的新增等差子数组个数 int totalSlices = 0; // 累计总的等差子数组数量 // 从索引2开始遍历（因为至少需要3个元素） for (int i = 2; i < n; i++) { // 判断是否满足等差条件：当前差 == 前一段差 if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) { // 可以延续之前的等差序列 dp[i] = dp[i-1] + 1; } // 如果不满足，dp[i] 默认为0，无需赋值 // 累加到总结果 totalSlices += dp[i]; } return totalSlices; }}空间优化
由于 dp[i] 只依赖于 dp[i-1]，可以用一个变量代替整个数组。
class Solution { /** * 空间优化：使用滚动变量减少空间复杂度 * * @param nums 整数数组 * @return 等差数列子数组的总数 */ public int numberOfArithmeticSlices(int[] nums) { if (nums == null || nums.length < 3) { return 0; } int n = nums.length; int dp = 0; // 表示 dp[i-1] 的值 int totalSlices = 0; // 总的等差子数组数量 for (int i = 2; i < n; i++) { if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) { dp = dp + 1; // dp[i] = dp[i-1] + 1 } else { dp = 0; // 断开等差，重新计数 } totalSlices += dp; } return totalSlices; }}算法分析
算法过程
nums = [1,2,3,4] ：
totalSlices = dp[2] + dp[3] = 1 + 2 = 3
测试用例
public static void main(String[] args) { Solution solution = new Solution(); // 测试用例1：标准示例 int[] nums1 = {1, 2, 3, 4}; System.out.println(\"Test 1: \" + solution.numberOfArithmeticSlices(nums1)); // 3 // 测试用例2：无等差 int[] nums2 = {1, 2, 4, 5, 7}; System.out.println(\"Test 2: \" + solution.numberOfArithmeticSlices(nums2)); // 0 // 测试用例3：全相同（公差为0） int[] nums3 = {1, 1, 1, 1}; System.out.println(\"Test 3: \" + solution.numberOfArithmeticSlices(nums3)); // 3 // 子数组: [1,1,1], [1,1,1], [1,1,1,1] → 共3个 // 测试用例4：长度刚好3 int[] nums4 = {1, 3, 5}; System.out.println(\"Test 4: \" + solution.numberOfArithmeticSlices(nums4)); // 1 // 测试用例5：短数组 int[] nums5 = {1, 2}; System.out.println(\"Test 5: \" + solution.numberOfArithmeticSlices(nums5)); // 0 // 测试用例6：复杂情况 int[] nums6 = {1, 2, 3, 5, 7, 9}; System.out.println(\"Test 6: \" + solution.numberOfArithmeticSlices(nums6)); // 4 }关键点
-
dp定义：
dp[i]不是“最长长度”，而是“以i结尾的新增等差子数组个数”。- 比如
[1,2,3,4]中：dp[2]=1→[1,2,3]dp[3]=2→[2,3,4],[1,2,3,4]
-
为什么
dp[i] = dp[i-1] + 1？- 假设已有
k个以i-1结尾的等差子数组。 - 当前值能延续等差，则每个都可以延长一位，变成新的等差子数组（+k 个）。
- 再加上新形成的
[i-2,i-1,i]这个长度为3的子数组（+1 个）。 - 所以总共新增
k+1个 →dp[i] = dp[i-1] + 1
- 假设已有
-
边界处理：
- 数组长度 < 3 时直接返回 0。
- 循环从
i=2开始，避免越界。
-
公差可以为负或零：
[5,3,1]是公差为 -2 的等差数列。[2,2,2]是公差为 0 的等差数列。
常见问题
1. 为什么不能直接统计所有长度≥3的子数组再判断？
- 时间复杂度会达到 O(n³)，对大数据不友好。
- DP 方法是 O(n)，效率更高。
2. 如何验证某个子数组是等差？
- 检查相邻元素差是否相等即可：
for (int j = start+1; j < end; j++) { if (nums[j] - nums[j-1] != diff) break;}
3. 是否可以扩展到二维数组？
- 可以，但需要分别检查行、列、对角线方向的等差子序列，逻辑更复杂。
总结
本题是动态规划的经典应用，核心在于理解 dp[i] 的含义——“新增的等差子数组个数”。掌握这种“增量思维”有助于解决许多连续子数组计数类问题。
