Python DP solution


  • 4
    Z
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        opt, i = [0,0], 1
        for j in xrange(2,len(A)):
            if A[j]-A[j-1] == A[j-1]-A[j-2]:
                opt.append(opt[j-1]+i)
                i += 1
            else:
                opt.append(opt[j-1])
                i = 1
        return opt[-1]

  • 10
    Z

    @zhan430 Why not use a variable instead of an array?

    class Solution(object):
        def numberOfArithmeticSlices(self, A):
            curr, sum = 0, 0
            for i in range(2,len(A)):
                if A[i]-A[i-1] == A[i-1]-A[i-2]:
                    curr += 1
                    sum += curr
                else:
                    curr = 0
            return sum
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.