来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
题目要求输出等差数列所有情况数（包含等差序列子序列），且满足满足 0 ≤ P0 < P1 < ... < Pk < N，k>=2
输入：[2, 4, 6, 8, 10]
输出：7
解释：
所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
我首先记录下我的思路，因为要输出所有可能的等差序列的可能，所以我想到用做差法，记录每个元素与数组此元素后的元素的差值，通过数组元素之间差值可以找到等差序列，不过写代码的时候逻辑没写出来：
1 from collections import defaultdict 2 class Solution: 3 def numberOfArithmeticSlices(self, A) -> int: 4 d = defaultdict(list) 5 for i in range(len(A)): 6 for j in range(i+1,len(A)): 7 dis = A[j] - A[i] 8 d[A[i]].append(dis) 9 print(d) 10 #defaultdict(<class 'list'>, {2: [2, 4, 6, 8], 4: [2, 4, 6], 6: [2, 4], 8: [2]}) 11 print(d.get(8)) #[2] 12 for idx,key in enumerate(d.values()): 13 record = [] 14 for j in range(len(key)): 15 if A[idx] + key[j] == A[j+1]: 16 record.append(A[idx]) 17 record.append(A[j+1]) 18 if key[j] in d.get(A[j+1]) : 19 record.append() 20 a = Solution().numberOfArithmeticSlices([2,4,6,8,10])
record用来记录符合等差序列的元素，但是超过三个元素，第四个元素怎么寻找已经束手无策，学习下也是用字典不同思路其他大佬的代码。
思路
这题思路很简单，对于每个可以作为等差数列结尾的元素，我们为它维护一个字典，这个字典的key是等差数列的公差，值是公差为key的不同等差数列的个数。
以：0，1，2，3，4 为例， 假设我们以4作为等差数列的结尾元素，那公差可能为1, 2， 对应的数列分别是[(2,3),(1,2,3),(0,1,2,3)],[(0,2)]，对应的字典就是{1:3,2:1}
也就是如果我们在遇到元素4的时候已经计算好了这个字典，那就知道以4为结尾的等差数列个数应该+4；
同时我们能够根据这个信息更新以5，6结尾的等差数列个数, 进而更新相应的字典。
以0,1,2,3,4, 为例， 开始时的字典为{},当读完0,1之后的字典应为{2:{1:1}}, 表明，以2为结尾元素，公差为1的备选等差数列为1个；读取完2之后的字典应为：
{2:{1:1},3:{1:2},4:{2:1}} 一次类推；
整体代码也很简单，复杂度为O(n^2), 原因是可作为结尾的元素至多有n个。运行时间和空间均超过100%的python代码。
1 class Solution: 2 def numberOfArithmeticSlices(self, A: List[int]) -> int: 3 ans=0 4 pesudo_dict={} 5 num_dict={} 6 num_set=set(A) 7 for i in range(len(A)): 8 if A[i] in pesudo_dict: 9 ans+=num_dict[A[i]] 10 for seq in pesudo_dict[A[i]]: 11 next_num=A[i]+seq 12 cnt=pesudo_dict[A[i]][seq] 13 next_dict=pesudo_dict.setdefault(next_num,{}) 14 next_dict[seq]=next_dict.setdefault(seq,0)+cnt 15 num_dict[next_num]=num_dict.setdefault(next_num,0)+cnt 16 for j in range(i): 17 seq=A[i]-A[j] 18 next_num=2*A[i]-A[j] 19 if next_num not in num_set: 20 continue 21 next_dict=pesudo_dict.setdefault(next_num,{}) #和get()类似, 但如果键不存在于字典中，将会添加键并将值设为default f={},f[2] = f.setdefault(1,0)+1 #{1:0,2:1} 22 next_dict[seq]=next_dict.setdefault(seq,0)+1 23 num_dict[next_num]=num_dict.setdefault(next_num,0)+1 24 return ans 25 26 作者：streamer-AP 27 链接：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence/solution/python-zi-dian-jie-fa-by-streamer-ap/ 28 来源：力扣（LeetCode） 29 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
假设输入为[0,1,2,3,4]
num_set = {0,1,2,3,4}
1) i = 0, j = 0;
2) i = 1, j = 0 ;seq = 1,next_num = 2(这里利用等差公式性质很关键a + c =2b )，
next_dict=pesudo_dict.setdefault(next_num,{}) #{2:{}} 创建一个以数字2结尾的 {}
next_dict[seq]=next_dict.setdefault(seq,0)+1 #pesudo_dit = {2:{1:1}} 以数字2结尾的差值为1的数列有1个
num_dict[next_num]=num_dict.setdefault(next_num,0)+1 #{2:1}
3) 方法不熟悉没看懂
动态规划，两种方法实现，但是dp[i][k]都是表示到数组第i为底公差为k的超过长度3的个数
思路一：直接转移方程
dp[i][k] += 1 + dp[j][k], j < i
思路二：记录元素的索引号
这样我们可以算出公差 k = A[i] - A[j]，找A[j] - d元素有几个(这里都是组成3个公差的个数)，在加上A[j][k]的个数就是A[i][k]，
思路一
dp[i][k]理解为底为A[i],公差为k的长度大于等于2的“等差数列”的个数更合适，而且底在右，顶在左。比如对于[1,2,3]，dp[1][1] += dp[0][1] + 1 = 0 + 1,这里的1个就指的是[1,2]
1 class Solution: 2 def numberOfArithmeticSlices(self, A: List[int]) -> int: 3 from collections import defaultdict 4 dp = [defaultdict(int) for _ in range(len(A))] 5 res = 0 6 for i in range(len(A)): 7 for j in range(i): 8 diff = A[i] - A[j] 9 dp[i][diff] += dp[j][diff] + 1 10 # 说明满足长度大于等于3 11 if diff in dp[j]: 12 res += dp[j][diff] 13 return res 14 15 作者：powcai 16 链接：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence/solution/dong-tai-gui-hua-er-chong-shi-xian-by-powcai/ 17 来源：力扣（LeetCode） 18 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
假设输入为[0,1,2,3,4]
dp =<class 'list'>: [defaultdict(<class 'int'>, {}), defaultdict(<class 'int'>, {}), defaultdict(<class 'int'>, {}), defaultdict(<class 'int'>, {}), defaultdict(<class 'int'>, {})]
1) i = 0 pass
2) i = 1,j = 0 diff = 1 dp[1][1] = d[1][1]+dp[0][1] +1 = 1
dp = <class 'list'>: [defaultdict(<class 'int'>, {1: 0}), defaultdict(<class 'int'>, {1: 1}), defaultdict(<class 'int'>, {}), defaultdict(<class 'int'>, {}), defaultdict(<class 'int'>, {})]
3) i = 2,j =0 diff = 2 dp[2][2] = dp[2][2]+dp[0][2]+1
dp=<class 'list'>: [defaultdict(<class 'int'>, {1: 0, 2: 0}), defaultdict(<class 'int'>, {1: 1}), defaultdict(<class 'int'>, {2: 1}), defaultdict(<class 'int'>, {}), defaultdict(<class 'int'>, {})]
i = 2,j=1 diff = 1 dp[2][1] = dp[2][1]+dp[1][1]+1
dp=<class 'list'>: [defaultdict(<class 'int'>, {1: 0, 2: 0}), defaultdict(<class 'int'>, {1: 1}), defaultdict(<class 'int'>, {2: 1, 1: 2}), defaultdict(<class 'int'>, {}), defaultdict(<class 'int'>, {})]
res =1
4)i = 3,j = 0 diff = 3 dp[3][0] = dp[3][0] +dp[0][3]+1
dp=<class 'list'>: [defaultdict(<class 'int'>, {1: 0, 2: 0, 3: 0}), defaultdict(<class 'int'>, {1: 1}), defaultdict(<class 'int'>, {2: 1, 1: 2}), defaultdict(<class 'int'>, {3: 1}), defaultdict(<class 'int'>, {})]
i = 3,j = 1 diff = 2 dp[3][3] = dp[3][3]+dp[1][3]+1
dp=<class 'list'>: [defaultdict(<class 'int'>, {1: 0, 2: 0, 3: 0}), defaultdict(<class 'int'>, {1: 1, 2: 0}), defaultdict(<class 'int'>, {2: 1, 1: 2}), defaultdict(<class 'int'>, {3: 1, 2: 1}), defaultdict(<class 'int'>, {})]
i = 3,j=2 diff = 1 dp[3][1] = dp[3][1]+dp[2][1]+1
dp=<class 'list'>: [defaultdict(<class 'int'>, {1: 0, 2: 0, 3: 0}), defaultdict(<class 'int'>, {1: 1, 2: 0}), defaultdict(<class 'int'>, {2: 1, 1: 2}), defaultdict(<class 'int'>, {3: 1, 2: 1, 1: 3}), defaultdict(<class 'int'>, {})]
res = res + dp[2][1]
思路二
1 class Solution: 2 def numberOfArithmeticSlices(self, A: List[int]) -> int: 3 from collections import defaultdict 4 import bisect 5 n = len(A) 6 lookup = defaultdict(list) 7 dp = [defaultdict(int) for _ in range(n)] 8 res = 0 9 # 记录每个元素的位置 10 for idx, val in enumerate(A): 11 lookup[val].append(idx) 12 for i in range(n): 13 for j in range(i): 14 diff = A[i] - A[j] 15 target = A[j] - diff 16 # 先找 和 A[j], A[i]组成三个数组个数 17 # for idx in lookup[target]: 18 # if idx < j: 19 # dp[i][diff] += 1 20 # else: 21 # break 22 dp[i][diff] += bisect.bisect_left(lookup[target], j) # 可以用二分找个数 23 # 加上 第j位置公差为diff个数 24 dp[i][diff] += dp[j][diff] 25 # 统计个数 26 for val in dp[i].values(): 27 res += val 28 return res 29 30 作者：powcai 31 链接：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence/solution/dong-tai-gui-hua-er-chong-shi-xian-by-powcai/ 32 来源：力扣（LeetCode） 33 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
参考：
Python 字典方法使用：https://www.cnblogs.com/keye/p/13216568.html