求一個數(shù)列中最長的等差數(shù)列子串長度，python的dict的妙用
參考了Discussion -> https://leetcode.com/problems/longest-arithmetic-subsequence/solutions/3671637/hashmap-video-java-c-python/
1 #1027
2 #Runtime: 2571 ms (Beats 66.4%)
3 #Memory: 45.1 MB (Beats 60.38%)
4
5 class Solution(object):
6 def longestArithSeqLength(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: int
10 """
11 ans = 0
12 n = len(nums)
13 dp = [defaultdict(int) for _ in range(n)]
14 for i in range(n):
15 for j in range(i):
16 dif = nums[j] - nums[i]
17 dp[i][dif] = dp[j].get(dif, 1) + 1
18 ans = max(ans, dp[i][dif])
19 return ans