1 題目描述
若一個(gè)數(shù)列至少有三個(gè)元素,且任意相鄰兩元素的差相等,則該數(shù)列為一個(gè)等差數(shù)列。
例如,如下三個(gè)數(shù)列即為等差數(shù)列:
1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9
如下數(shù)列不是等差數(shù)列:
1, 1, 2, 5, 7
現(xiàn)給定一個(gè)以0為起始索引,包含N個(gè)數(shù)的數(shù)組A。數(shù)組的切片(P, Q)為滿足規(guī)則(0 <= P < Q < N)的任意整數(shù)組合。
若數(shù)組A的切片(P, Q)滿足如下規(guī)則,則稱該數(shù)組切片是一個(gè)等差數(shù)列:
A[P], A[p + 1], ..., A[Q - 1], A[Q]是一個(gè)等差數(shù)列,且P + 1 < Q。
代碼函數(shù)需返回?cái)?shù)組A的等差數(shù)列的個(gè)數(shù)。
例子:
輸入:
A = [1, 2, 3, 4]
輸出:
3
釋義:
A中有3個(gè)等差數(shù)列切片:[1, 2, 3],[2, 3, 4]與[1, 2, 3, 4]。
題目出處:
https://leetcode.com/problems/arithmetic-slices/
2 解決思路
首先從A中找出有幾個(gè)最長等差數(shù)列。
a)首先定義slices用來存儲(chǔ)所有最長的等差slice,slice初始為2,初始間隔preInterval為a[1]-a[0];
b)從第3個(gè)元素開始遍歷A,若當(dāng)前元素與前一個(gè)元素的差interval與preInterval相等,則slice+1;若interval與preInterval不等,則判斷是否將當(dāng)前slice合入slices,并將slice賦值為2,preInterval賦值為interval,遍歷下一個(gè)元素;
c)直至遍歷到最后一個(gè)元素,若interval與preInterval相等,則判斷是否將當(dāng)前slice合入slices。
對(duì)其中一個(gè)滿足規(guī)則的最長等差數(shù)列,計(jì)算其中所有滿足等差數(shù)列規(guī)則的切片個(gè)數(shù)的計(jì)算函數(shù)為。

3 golang實(shí)現(xiàn)代碼
綜上,整個(gè)邏輯的實(shí)現(xiàn)代碼為:
https://github.com/olzhy/leetcode/blob/master/413_Arithmetic_Slices/test.go

原文:https://leileiluoluo.com/posts/leetcode-arithmetic-slices.html