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


  • 0
    S

    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,
    [1,2,3,4,5]
    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.