413、等差数列划分
数组 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 中所有为等差数组的子数组个数。
示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
题解
子数组是必须是连续子序列。
1、暴力枚举
先两两计算差值d，在两两枚举查找，剩余满足差值为d的数列。
- 代码
// java
class Solution {
public int numberOfArithmeticSlices(int[] A) {
int count = 0;
// 遍历相邻元素，求其差
for (int s = 0;s < A.length - 2;s++) {
// 求差值
int d = A[s+1] - A[s];
// 枚举所以有相邻元素,求从s开始可以有多少组差为d的等差数列
for (int e = s+2;e < A.length;e++) {
// 遍历[s+1,e]的元素
int i = 0;
for (i = s+1;i <= e;i++) {
// 判断是否构成等差数列
if (A[i] - A[i - 1] != d) {
// 一旦有不符合的元素就结束。
break;
}
}
// 找到了可以成为等差数列的项
if (i > e) {
count++;
}
}
}
return count;
}
}
2、优化后的暴力
第三层循环：
其实是可以不用重复的判断区间 [s+1,e] 的，只需要判断最后一对元素的差值是不是跟之前区间中的差值相等就可以了。
- 代码
// java
class Solution {
public int numberOfArithmeticSlices(int[] A) {
int count = 0;
// 遍历相邻元素，求其差
for (int s = 0;s < A.length - 2;s++) {
// 求差值
int d = A[s+1] - A[s];
// 枚举所以有相邻元素,求从s开始可以有多少组差为d的等差数列
for (int e = s+2;e < A.length;e++) {
// 直接判断最后一堆元素是否满足
if (A[e]- A[e-1] == d) {
count++;
} else {
// 只要有一个元素不满足构成等差数列，就可以直接结束了。
break;
}
}
}
return count;
}
}
3、递归
- 代码
// java
public class Solution {
int sum = 0;
public int numberOfArithmeticSlices(int[] A) {
slices(A, A.length - 1);
return sum;
}
public int slices(int[] A, int i) {
if (i < 2)
return 0;
int ap = 0;
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
// 递归查找
ap = 1 + slices(A, i - 1);
sum += ap; // 累加子数组的数量
} else {// 不满足等差，出现了断层
// 递归查找下一位的值
slices(A, i - 1);
}
return ap;
}
}
// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/arithmetic-slices/solution/deng-chai-shu-lie-hua-fen-by-leetcode/
}
4、一维动态规划
$dp[i]$ 用来存储在区间 $(k,i)$， 而不在区间 $(k,j)$中等差数列的个数，其中 $j<i$。
对于第 i 个元素，判断这个元素跟前一个元素的差值是否和等差数列中的差值相等。如果相等，那么新区间中等差数列的个数即为 $1+dp[i-1]$。sum 同时也要加上这个值来更新全局的等差数列总数。
链接：https://leetcode-cn.com/problems/arithmetic-slices/solution/deng-chai-shu-lie-hua-fen-by-leetcode/
- 代码
// java
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
int[] dp = new int[A.length];
int sum = 0;
for (int i = 2; i < dp.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = 1 + dp[i - 1];
sum += dp[i];
}
}
return sum;
}
}
// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/arithmetic-slices/solution/deng-chai-shu-lie-hua-fen-by-leetcode/
// 由于状态只是相邻项相关，可以进行空间优化
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
int dp = 0;
int sum = 0;
for (int i = 2; i < A.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp = 1 + dp;
sum += dp;
} else
dp = 0;
}
return sum;
}
}
// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/arithmetic-slices/solution/deng-chai-shu-lie-hua-fen-by-leetcode/
}
5、公式计算
通过 dp 方法，我们观察到对于 k 个连续且满足等差条件的元素，每次 sum 值分别增加 $1, 2, 3, …, k$因此，与其每次更新 sum 值，只需要用变量 count 来记录有多少个满足等差条件的连续元素，之后直接把 sum 增加 $count*(count+1)/2$ 就可以了。
链接：https://leetcode-cn.com/problems/arithmetic-slices/solution/deng-chai-shu-lie-hua-fen-by-leetcode/
- 代码
// java
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
int count = 0;
int sum = 0;
for (int i = 2; i < A.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
count++;// 累加相邻等差的子序列长度
} else {
// 用公式求出长度维count的等差子序列可以构成的等差数组的个数
sum += (count + 1) * (count) / 2;
// 重置
count = 0;
}
}
// 累加最后一个等差子序列
return sum += count * (count + 1) / 2;
}
}
// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/arithmetic-slices/solution/deng-chai-shu-lie-hua-fen-by-leetcode/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
