A clear python solution with a little math


  • 2
    M

    The key idea is to find blocks with the same difference, i.e., for [1,2,3,4,7,9,11,13,15], the [1,2,3,4] and [7,9,11,13,15] are two blocks with difference 1 and 2, respectively.

    Once we know the lengths, which are 4 and 5, then the number of slices are just (n-1)(n-2)/2, which is, n-2 + n-3 + ... + n-(n-1) for each n. Then just create a list of maximum lengths of blocks and apply the above formula. Enjoy!

    def numberOfArithmeticSlices(self, A):
        if len(A) < 3: return 0
        ns, n = [], 0
        for i in range(2, len(A)):
            if A[i] - A[i-1] == A[i-1] - A[i-2]:
                n += 1
            else:
                if n >= 1: ns.append(n+2)
                n = 0
        else:
            if n >= 1: ns.append(n+2)
        return int(sum(list(map(lambda x: (x-1)*(x-2)/2, ns))))

Log in to reply
 

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