若一个数列至少有三个元素,且任意相邻两元素的差相等,则该数列为一个等差数列。
例如,如下三个数列即为等差数列:
1, 3, 5, 7, 9 7, 7, 7, 7 3, -1, -5, -9
如下数列不是等差数列:
1, 1, 2, 5, 7
现给定一个以0为起始索引,包含N个数的数组A。数组的切片(P, Q)为满足规则(0 <= P < Q < N)的任意整数组合。
若数组A的切片(P, Q)满足如下规则,则称该数组切片是一个等差数列:
A[P], A[p + 1], ..., A[Q - 1], A[Q]是一个等差数列,且P + 1 < Q。
代码函数需返回数组A的等差数列的个数。
例子:
输入:
A = [1, 2, 3, 4]
输出:
3
释义:
A中有3个等差数列切片:[1, 2, 3],[2, 3, 4]与[1, 2, 3, 4]。
题目出处:
https://leetcode.com/problems/arithmetic-slices/
首先从A中找出有几个最长等差数列。
a)首先定义slices用来存储所有最长的等差slice,slice初始为2,初始间隔preInterval为a[1]-a[0];
b)从第3个元素开始遍历A,若当前元素与前一个元素的差interval与preInterval相等,则slice+1;若interval与preInterval不等,则判断是否将当前slice合入slices,并将slice赋值为2,preInterval赋值为interval,遍历下一个元素;
c)直至遍历到最后一个元素,若interval与preInterval相等,则判断是否将当前slice合入slices。
对其中一个满足规则的最长等差数列,计算其中所有满足等差数列规则的切片个数的计算函数为。
综上,整个逻辑的实现代码为:
https://github.com/olzhy/leetcode/blob/master/413_Arithmetic_Slices/test.go
原文:https://leileiluoluo.com/posts/leetcode-arithmetic-slices.html