image.png
這題是放到動態(tài)規(guī)劃的題型里了。但是根本不用動態(tài)規(guī)劃做崎页。
這題的關(guān)鍵是：
- 至少3個元素
- 必須是相鄰的 （這個條件讓題目簡單不少，如果不是連續(xù)的就比較麻煩了）
簡單的思路
- 把相鄰元素的差值都求出來
- 計算相鄰元素差值相同的元素個數(shù)
- 行數(shù) = 相鄰元素個數(shù) + 1 - 3 腰埂， 然后從行數(shù) 一直遞減加到1
比如5個數(shù)組成等差數(shù)列 飒焦， 行數(shù) = 5 - 3 + 1 = 3，
也就是 3 + 2 + 1 = 6 種 等差數(shù)列
具體的草稿紙寫寫就看出來了
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里比較大的那個數(shù)的位置對上
}
int len = 1;
int sum = 0;
for (int i = 2; i < diff.length; i++) {
// 第二個條件是在數(shù)組結(jié)尾即使跟前面一樣屿笼，也必須進(jìn)行后面的求和
if (diff[i] == diff[i -1] && i < diff.length - 1) {
len++;
} else {
// len + 1 是實際數(shù)組中等差數(shù)列的長度
// (len + 1) - 3 + 1 是等差數(shù)列中能容下長度為3的序列的長度牺荠。
// 比如
// nums[] = 1，3刁卜，5志电，7，9蛔趴，10挑辆，11
// diff[] = 0，2孝情，2鱼蝉，2，2箫荡， 1魁亦， 1
// 對應(yīng)的 len + 1 就是 5， 和 2
// row = 5 - 3 + 1 = 3羔挡， 也就是說能出現(xiàn)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的組合數(shù)是 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});
}
}
