|
如果一個數(shù)列至少有三個元素，并且任意兩個相鄰元素之差相同,，則稱該數(shù)列為等差數(shù)列,。 例如，以下數(shù)列為等差數(shù)列: 1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9 以下數(shù)列不是等差數(shù)列,。 1, 1, 2, 5, 7 求函數(shù)中返回數(shù)組 A 中所有為等差數(shù)組的子數(shù)組個數(shù),。 示例: A = [1, 2, 3, 4]
返回: 3, A 中有三個子等差數(shù)組: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。 答案：
1public int numberOfArithmeticSlices(int[] A) {
2 int curr = 0, sum = 0;
3 for (int i = 2; i < A.length; i++)
4 if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
5 curr += 1;
6 sum += curr;
7 } else {
8 curr = 0;
9 }
10 return sum;
11}
解析：
要想構(gòu)成等差數(shù)列,，至少要3個元素,，所以i是從2(也就是第三個元素)開始判斷，curr表示的是已經(jīng)構(gòu)成的等差數(shù)列的子數(shù)組的個數(shù),，如果不能構(gòu)成等差數(shù)列就讓curr等于0,，就不再計入總數(shù)sum了。如果能構(gòu)成等差數(shù)列就讓curr加1,，然后再加入到總數(shù)sum中,，這里curr為什么是要加1，我們畫個圖來分析一下
或者代碼也可以更簡潔一些,，如下
1public int numberOfArithmeticSlices(int[] A) {
2 int curr = 0, sum = 0;
3 for (int i = 2; i < A.length; i++) {
4 curr = (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) ? curr + 1 : 0;
5 sum += curr;
6 }
7 return sum;
8}
寫法上雖然有點差別,，但思路其實都是一樣的，下面我們再來把它改為遞歸的寫法
1public int numberOfArithmeticSlices(int[] A) {
2 return slices(A, A.length - 1);
3}
4
5public int slices(int[] A, int i) {
6 if (i < 2)
7 return 0;
8 if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
9 return slices(A, i - 1) * 2 - slices(A, i - 2) + 1;
10 } else {
11 return slices(A, i - 1);
12 }
13}
這種執(zhí)行效率太差,，多次重復(fù)計算,，很容易超時，我們還可以在優(yōu)化一下
1int sum = 0;
2
3public int numberOfArithmeticSlices(int[] A) {
4 slices(A, A.length - 1);
5 return sum;
6}
7
8public int slices(int[] A, int i) {
9 if (i < 2)
10 return 0;
11 int count = 0;
12 if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
13 count = 1 + slices(A, i - 1);
14 sum += count;
15 } else {
16 slices(A, i - 1);
17 }
18 return count;
19}
|
