給出一列數(shù)和等差數(shù)列的相鄰數(shù)之差，問符合這個(gè)差值的最長的子串長度，DP+hash
1 #1218
2 #Runtime: 499 ms (Beats 50%)
3 #Memory: 24.2 MB (Beats 100%)
4
5 class Solution(object):
6 def longestSubsequence(self, arr, difference):
7 """
8 :type arr: List[int]
9 :type difference: int
10 :rtype: int
11 """
12 ans = 0
13 num = {}
14 for i in range(len(arr)):
15 t = arr[i]
16 if t - difference in num:
17 num[t] = num[t - difference] + 1
18 else:
19 num[t] = 1
20 ans = max(ans, num[t])
21 return ans