Python Solution from the Author


  • 3
    S

    I see a lot people got TLE and it's been 2 weeks since the contest. So I am going to post my official solution.

    class Solution(object):
        def numberOfArithmeticSlices(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
    
            lookup = {}
    
            for i, a in enumerate(A):
                if a in lookup:
                    lookup[a].append(i)
                else:
                    lookup[a] = [i]
    
            dp = []
            for _ in range(len(A)):
                dp.append({})
    
            for k, num in enumerate(A):
                for i in range(0, k):
                    diff = A[k] - A[i]
                    X = A[i] - diff
                    if X in lookup:
                        for index in lookup[X]:
                            if index < i:
                                dp[k][diff] = dp[k].get(diff, 0) + 1
    
                    if diff in dp[i]:
                        dp[k][diff] = dp[k].get(diff, 0) + dp[i][diff]
    
            res = 0
            for x in dp:
                for k in x:
                    res += x[k]
    
            return res

  • 0

    The idea is cool! But I prefer this style because it's a little bit more "Python" :-P:

    import collections
    class Solution(object):
        def numberOfArithmeticSlices(self, A):
            dp, lookup, res = [{} for _ in range(len(A))], collections.defaultdict(list), 0
            for i in range(len(A)):
                lookup[A[i]].append(i)
            for i in range(len(A)):
                for j in range(i):
                    diff = A[i] - A[j]
                    X = A[j] - diff 
                    if X in lookup:
                        for idx in lookup[X]:
                            if idx < j:
                                dp[i][diff] = dp[i].get(diff, 0) + 1
                    if diff in dp[j]:
                        dp[i][diff] = dp[i].get(diff, 0) + dp[j][diff]
            for x in dp:
                for k in x:
                    res += x[k]
            return res
    

  • 0
    M

    Your code is brilliant !!! On the basis of it, I modified a bit... , 400ms

    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        lookup = collections.defaultdict(list)
        for i, a in enumerate(A):
            lookup[a] += i,
        dp = [{} for _ in range(len(A))]
    
        for k, num in enumerate(A):
            for i in range(0, k):
                diff = A[k] - A[i]
                X = A[i] - diff
                if X in lookup:
                    for index in lookup[X]:
                        if index < i:
                            dp[k][diff] = dp[k].get(diff, 0) + 1
                        else: break
                if diff in dp[i]:
                    dp[k][diff] = dp[k].get(diff, 0) + dp[i][diff]
        return sum([x[k] for x in dp for k in x])
    

  • 0
    S

    it would have helped if you had given optimal substructure and recurrence formula


Log in to reply
 

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