One round O(n) time O(1) space, easy to understand

  • 0

    For each element in the array, we add number of all arithmetic slices ending at this element according to the length of longest one. For example,
    When we reach 4, the current length of longest slice is 4([1,2,3,4]), so we need to add 4-2 to result. ([2,3,4], [1,2,3,4]).

    class Solution(object):
    def numberOfArithmeticSlices(self, A):
    res = 0
    curlen = 1 #the length of arithmetic slice ending at this element
    for i in xrange(1, len(A)):
    tmp = A[i] - A[i-1]
    #if this is the first round
    if curlen == 1:
    step = tmp
    curlen += 1
    #if current element can extend the arithmetic slice
    elif tmp == step:
    curlen += 1
    res += curlen-2 #number of arithmetic slices ending at this element
    else: #if this step is not same, reset length and step
    curlen = 2
    step = tmp
    return res

Log in to reply

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