🚩传送门：https://leetcode-cn.com/problems/arithmetic-slices/

题目

如果一个数列至少有三个元素，并且 任意两个相邻 元素之差相同，则称该数列为等差数列。

例子 1：

以下数列为等差数列

1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9

例子 2：

以下数列不是等差数列

1, 1, 2, 5, 7

数组 A 包含 N 个数，且索引从 0 开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
如果满足以下条件，则称子数组(P, Q)为等差数组：

元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

函数要返回数组 A 中所有为等差数组的子数组个数。

示例 1：

A = [1, 2, 3, 4]

返回 : 3, A 中有三个子等差数组: **[**1, 2, 3**]**, **[**2, 3, 4**]** 以及自身 **[**1, 2, 3, 4**]**。

解题思路：暴力

根据暴力出奇迹，大力可挂机思想，直接暴力枚举所有情形，选出符合的情形，但效率低下 。

方法1：凶残的纯暴力

此代码过于凶残，确认过眼神是我写不出来的烂思路代码，故而放弃此种方法

复杂度分析

时间复杂度：，其中 [LeetCode]Dp413 等差数列划分 - 图1 为数组 [LeetCode]Dp413 等差数列划分 - 图2 的长度 。

对于每一对元素，都需要遍历它们之间的所有元素。

空间复杂度：，只需额外开辟常数个空间 。

方法1：优雅的暴力

双指针滑动窗口，一直向右检查是否构成等差区间，若不构成 i 指针右移，构成 j 右移且 count++ ，每次不构成重置时候，j=i+2 原因就是：题目要求必须 3 个以上才能构成等差区间 。
image.png

复杂度分析

时间复杂度：，其中 [LeetCode]Dp413 等差数列划分 - 图4 为数组 [LeetCode]Dp413 等差数列划分 - 图5 的长度 。算法有两层循环 。

空间复杂度：，只需额外开辟常数个空间 。

官方代码

  1. public class Solution {
  2.     public int numberOfArithmeticSlices(int[] A) {
  3.         int count = 0;
  4.         //数列的第一个数起点
  5.         for (int i = 0; i < A.length - 2; i++) {
  6.             int Difference = A[s + 1] - A[s];
  7.             //从数列的第三个数开始计算是否造成等差
  8.             for (int j = i + 2; j < A.length; j++) {
  9.                 if (A[j] - A[j - 1] == Difference)
  10.                     count++;
  11.                 else
  12.                     break;
  13.             }
  14.         }
  15.         return count;
  16.     }
  17. }

解题思路：递归

新瓶装旧酒，总体还是把握 以 nums[i] 为结尾的等差数列的个数。

定义变量 sum 来记录数组 A 中所有等差数列的个数。

定义一个递归方法 slice(A,i) ，在数组A 的 (0,i) 区间内，来求以 nums[i] 为结尾的等差数列的个数。

  • 递归进去，区间个数不到 3 个，不能构成等差区间，直接返回 0 结果
  • 检查最末尾的三项是否构成等差区间
    • 构成等差区间，记录当前三项的 1，接着去缩小规模计算以 nums[i-1] 结尾的个数
    • 不构成缩小规模,检查 nums[i-1] 结尾的个数

备注：不构成就是默认值 0 ,构成就是返回的 ap 值

  1. public class Solution {
  2.     int sum = 0;
  3.     public int numberOfArithmeticSlices(int[] A) {
  4.         slices(A, A.length - 1);
  5.         return sum;
  6.     }
  7.     public int slices(int[] A, int i) {
  8.         //个数不能构成等差区间,直接返回0结果
  9.         if (i < 2)
  10.             return 0;
  11.         //临时记录以nums[i]结尾所能构成的总个数
  12.         int ap = 0;
  13.         //检查最末尾的三项是否构成等差区间
  14.         if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
  15.             //构成记录当前三项的1,接着去缩小规模计算以nums[i-1]结尾的个数
  16.             ap = 1 + slices(A, i - 1);
  17.             sum += ap;
  18.         } else//不构成缩小规模,检查nums[i-1]结尾的个数
  19.             slices(A, i - 1);
  20.         //不构成就是默认值0,构成就是返回的ap值
  21.         return ap;
  22.     }
  23. }

🚩解题思路：动态规划

我们观察到区间 (0,i) 中等差数列的个数只和这个区间中的元素有关。因此，可以用动态规划来解决。

👉 定义 为以 为结尾所能构成的等差区间的个数

对于第 i 个元素，判断第 i 元素跟 i-1 个元素的差值是否和等差数列中的差值相等。若相等，那么说明第 i 个元素可以和前面的元素构成等差数列区间 。对于以 nums[i-1] 为结尾所能构成的等差区间的序列，只要加上nums[i] 就可以构成新的等差序列，而且 num[i-2],num[i-1],num[i] 会形成新的一个等差序列，故dp[i]等于 1+dp[i-1] 。

sum 只需要记录下以每个 nums[i] 为结尾构成的总数，就是题目答案。

状态转移方程：

复杂度分析

  1. 普通动态规划

时间复杂度：，其中 [LeetCode]Dp413 等差数列划分 - 图6 为数组 [LeetCode]Dp413 等差数列划分 - 图7 的长度 。一次遍历。

空间复杂度：，只需开辟 个空间 。

  1. 滚动数组优化

时间复杂度：，其中 [LeetCode]Dp413 等差数列划分 - 图8 为数组 [LeetCode]Dp413 等差数列划分 - 图9 的长度 。一次遍历。

空间复杂度：，只需开辟常数个空间 。

官方代码 [ 动态规划 ]

  1. public class Solution {
  2.     public int numberOfArithmeticSlices(int[] A) {
  3.         int[] dp = new int[A.length];
  4.         int sum = 0;
  5.         for (int i = 2; i < dp.length; i++) {
  6.             if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
  7.                 dp[i] = 1 + dp[i - 1];
  8.                 sum += dp[i];
  9.             }
  10.         }
  11.         return sum;
  12.     }
  13. }

官方代码 [ 动态规划：滚动数组空间优化 ]

  1. public class Solution {
  2.     public int numberOfArithmeticSlices(int[] A) {
  3.         int dp = 0;
  4.         int sum = 0;
  5.         for (int i = 2; i < A.length; i++) {
  6.             if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
  7.                 dp = 1 + dp;
  8.                 sum += dp;
  9.             } else
  10.                 dp = 0;
  11.         }
  12.         return sum;
  13.     }
  14. }

🚩解题思路：特解

此思路不具共性，只针对此题有效，效率最快最好 。
连续性排列组合种类个数
🦄不难发现（小爷我一眼就看出来了），某区间的 等差数组的子数组个数 与这一小段区间的 个数 有关，故遍历区间来检查相邻元素之间的差值是否相等并统计区间个数，公式： ，
计算求出当前区间 的所有可能性，因此总结果

现在解释公式：

假设小区间为：1 3 5 7 9 此区间均构成等差 那么连续性的排列组合有多少种呢？ {1} 、{3}、 {5}、 {7}、 {9} 👉 5种 [ ×个数太少 ] {1，3}、 {3，5}、{5，7}、{7，9} 👉 4种 [ ×个数太少 ] {1，3，5}、{3，5，7}、{5，7，9} 👉 3种 [ √符合情况 ] …… 不难发现，就是 5+4+3+2+1 的组合方式，但是题目说了必须连续 3 个数字以上，说明组合方式 3+2+1

3+2+1 满足

由归纳法： ① 5项 3+2+1 ② 推理 n 项 （n-2）+（n-3）+….+2+1 ③ 根据等差求和公式，上式和 {[1+(n-2)]×(n-2)}/2 经过整理 [(n-1)×(n-2)]/2

复杂度分析

时间复杂度：，其中 [LeetCode]Dp413 等差数列划分 - 图10 为数组 [LeetCode]Dp413 等差数列划分 - 图11 的长度 。只需要一次遍历 。

空间复杂度：，只需额外开辟常数个空间 。

我的代码

🚩优雅的代码

  1. public class Solution {
  2.     public static int numberOfArithmeticSlices(int[] nums) {
  3.         int Tempnums=1,Difference,res=0;
  4.         if(nums.length<3)return 0;
  5.         //为了方便从第2个数开始计算,即使2成立,公式结果也是0,不影响结果
  6.         Difference=nums[1]-nums[0];
  7.         for (int i = 1; i < nums.length; i++) {
  8.             //区间差值相等,等差区间相连
  9.             if(Difference==nums[i]-nums[i-1]) Tempnums++;//个数上增
  10.             //区间差值不等,等差区间断开
  11.             else{
  12.                 res+=((Tempnums-2)*(Tempnums-1))/2;         //计算区间内种类
  13.                 Tempnums=2;                                 //哨兵更新为 2
  14.                 Difference=nums[i]-nums[i-1];             //并更新差值
  15.             }
  16.         }
  17.         //此处处理2种特殊情况,区间连续至结尾与数组最后一组数字不构成等差
  18.         return (res+=((Tempnums-2)*(Tempnums-1))/2);
  19.     }
  21.     public static void main(String[] args) {
  22.         int[]a={1, 3, 5,7,9,15,20,25,28,29};
  23.         System.out.println(numberOfArithmeticSlices(a));
  24.     }
  25. }
  26. //结果输出: 7