image.png
这题是放到动态规划的题型里了。但是根本不用动态规划做。
这题的关键是：
- 至少3个元素
- 必须是相邻的 （这个条件让题目简单不少，如果不是连续的就比较麻烦了）
简单的思路
- 把相邻元素的差值都求出来
- 计算相邻元素差值相同的元素个数
- 行数 = 相邻元素个数 + 1 - 3 ， 然后从行数 一直递减加到1
比如5个数组成等差数列 ， 行数 = 5 - 3 + 1 = 3，
也就是 3 + 2 + 1 = 6 种 等差数列
具体的草稿纸写写就看出来了
package leetcode.dp;
public class _413_arslice {
public int numberOfArithmeticSlices(int[] nums) {
int[] diff = new int[nums.length + 1];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1]; //diff里的值跟nums里比较大的那个数的位置对上
}
int len = 1;
int sum = 0;
for (int i = 2; i < diff.length; i++) {
// 第二个条件是在数组结尾即使跟前面一样，也必须进行后面的求和
if (diff[i] == diff[i -1] && i < diff.length - 1) {
len++;
} else {
// len + 1 是实际数组中等差数列的长度
// (len + 1) - 3 + 1 是等差数列中能容下长度为3的序列的长度。
// 比如
// nums[] = 1，3，5，7，9，10，11
// diff[] = 0，2，2，2，2， 1， 1
// 对应的 len + 1 就是 5， 和 2
// row = 5 - 3 + 1 = 3， 也就是说能出现3行组合情况
// 1，3，5，7，9可以分为
// 3个一组 1，3，5 3，5，7 5，7，9 （3）
// 4个一组 1，3，5，7 3，5，7，9 （2）
// 5个一组 1，3，5，7，9 （1）
//也就是说
// 1，3，5，7，9的组合数是 1 + 2 + 3， 也就是(row + 1) * row / 2
int row = len - 3 + 1 + 1;
sum += (row + 1) * row / 2;
len = 1;
}
}
return sum;
}
public static void main(String[] args) {
_413_arslice a = new _413_arslice();
a.numberOfArithmeticSlices(new int[] {1,3,5,7,9,10,11});
}
}
