给出一列数和等差数列的相邻数之差,问符合这个差值的最长的子串长度,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