# Python Solution from the Author

• 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``````

• 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
``````

• 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])
``````

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

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