Skip to content

413 Arithmetic Slices

413. Arithmetic Slices

题目: https://leetcode.com/problems/arithmetic-slices/

难度 : Medium

思路:

tag 是DP

数从 i 到 j 之间的这个arithmetic 数

我的方法时间复杂度比较高O(N^2),从 i 开始数它的arithmetic slice,每个i数一遍,到 j

AC代码

class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        n = len(A)
        if n < 3:
            return 0
        else:
            res = 0
            for i in range(n-2):
                for j in range(i+2,n):
                    if A[j] - A[j-1] == A[i+1] - A[i]:
                        res += 1
                    else:
                        break
            return res

应该可以优化到O(N)

不需要每个每个开始数,可以边数边移动

可以参考http://www.cnblogs.com/grandyang/p/5968340.html

O(N) 代码

class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        n = len(A)
        if n < 3:
            return 0
        else:
            res, cnt = 0, 2
            for i in range(2, n):
                if A[i] - A[i-1] == A[i-1] - A[i-2]:
                    print i, i-1, i-2
                    cnt += 1
                else:
                    if cnt > 2:
                        res += (cnt-1) * (cnt-2)  / 2
                    cnt = 2
            if cnt > 2: res += (cnt-1) * (cnt-2)  / 2
            return res




回到顶部