leetcode_413

发表于   |   分类于

Arithmetic Slices

题目戳这

题意

给一个数组A，求A的子序列中等差数列的个数(等差数列的要求是至少连续三个数字，相邻之间的差相等)

解法

查了下用O(n)时间效率的做法，发现好精妙啊。学习了。
比如有这么几个数组，以及它们的子序列等差数列个数：

[1,2,3] 1

[1,2,3,4] 3

[1,2,3,4,5] 6

[1,2,3,4,5,6] 10

通过观察发现，个数是有规律的，分别是1，3=1+2，6=3+3，10=6+4，即整体为等差数列的个数加一，则它包含的子序列的等差数列个数之差是一个差值为1的等差数列，从2开始，如果用公式表示，就是 F(n) = F(n-1) + add,add就是一个从2开始的等差数列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        alen = len(A)
        if alen < 3:
            return 0
        ans = 0
        tmp = 1
        for i in range(2, alen):
            if A[i] - A[i-1] == A[i-1] - A[i-2]: # 如果三个成等差数列
                ans += tmp
                tmp += 1
            else:
                tmp = 1
        
        return ans
        
        # print(res)