題目

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

難度

Medium

方法

如果3個數(shù)之間等差，則為數(shù)列。對于a1,a2,a3,a4,a5，將3個數(shù)歸為一組向后遍歷，a1a2a3為一個序列，seriesNum=1; a2a3a4有2個序列，即a2a3a4和a1a2a3a4，因此a2a3a4的seriesNum=2，同理，a3a4a5對應(yīng)的seriesNum=3。最后將各組的seriesNum相加則為總共的序列數(shù)。
注意[1,2,3,8,9,10]這種特殊情況

python代碼

class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        i = 2
        result = 0
        seriesNum = 0
        while i < len(A):
            if A[i-1]-A[i-2] == A[i]-A[i-1]:
                seriesNum += 1
                result += seriesNum
            else:
                seriesNum = 0
            i += 1

        return result

assert Solution().numberOfArithmeticSlices([1,2,3,4]) == 3
assert Solution().numberOfArithmeticSlices([1,2,3,4,5]) == 6
assert Solution().numberOfArithmeticSlices([1,2,3,8,9,10]) == 2