Python 10-lines, one-pass, time O(n), space O(1) solution


  • 0
    C

    Simply check the difference between adjacent elements.
    If it's different from the previous one, do:
    (1) update the counts
    (2) update the prediff and the head (the starting index of this prediff)

    def numberOfArithmeticSlices(self, A):
        if len(A) <= 2:
            return 0
        i, count, head, prediff = 2, 0, 0, A[1]-A[0]
        while i < len(A):
            diff = A[i] - A[i-1]
            if diff != prediff:
                count += (i-head-2)*(i-head-1)/2  #from head to i-1
                head, prediff = i-1, diff
            i += 1
        return count + (i-head-2)*(i-head-1)/2

Log in to reply
 

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