题目：如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A 包含 N 个数，且索引从 0 开始。该数组子序列将划分为整数序列 (P0, P1, ..., Pk)，P 与 Q 是整数且满足 0 ≤ P0 < P1 < ... < Pk < N。如果序列 A[P0]，A[P1]，...，A[Pk-1]，A[Pk] 是等差的，那么数组 A 的子序列 (P0，P1，…，PK) 称为等差序列。值得注意的是，这意味着 k ≥ 2。函数要返回数组 A 中所有等差子序列的个数。输入包含 N 个整数。每个整数都在 -231 和 231-1 之间，另外 0 ≤ N ≤ 1000。保证输出小于 231-1。
来源：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence/
法一：自己的代码 时间复杂度是(1 + n) * n / 2 即n方
思路：依次遍历A中的每个数，dp[i][k]表示以A[i]结尾公差为k（k != 0），长度至少为2的等差数列的个数-1，写dp转移方程之前，最重要的是要明确dp方程的定义。不同的dp转移方程直接决定了不同的方法。
from collections import defaultdict from typing import List class Solution: def numberOfArithmeticSlices(self, A: List[int]) -> int: size = len(A) # 注意这里，内部是个可变对象，不能直接乘，类似与[[0,1]] * 5这种，改一个就全改了 # dp = [defaultdict(lambda: -1)] * size dp = [] # 生成dp for i in range(size): dp.append(defaultdict(lambda: -1)) ans = 0 for i in range(1,size): # m是为了记录公差为0的等差数列的长度 m = 1 for j in range(i): # k是公差 k = A[i] - A[j] # 如果公差存在于以A[j]结尾的数列中，且公差不为0，则必定可以构成长为3的等差数列 if k in dp[j].keys(): if k != 0: # 这两行是关键， # 注意这里的两个1，第一个1是为了补上dp[j][k]中从-1到0的那一次，同ans = ans + dp[j][k] + 1中的这个1 # 第二个1表示由A[j] A[i]构成的数列，同下面m +=1的这个1 dp[i][k] = (dp[j][k] + 1) +1 + dp[i][k] # 加1是因为，初始值是从-1开始加的，如2:0表示公差为2，但它是长度为2的等差数列， # 所以加1是为了抵消从-1加1到0的那一次，因为它已经构成了长度为2的等差数列，只不过以前长度无法达到3，现在达到了 # 这里之所以分开写是因为，dp[i][k]表示的是 以A[i]结尾的长度为2的等差数列的个数-1 所以dp[j][k]+1就是在A[j]后 # 添加A[i]后，以A[j] A[i]结尾的等差数列的个数 ans = ans + dp[j][k] + 1 else: m += 1 else: dp[i][k] += 1 # 如果有公差为0的数列无法使用上述方法，直接记录数列的长度用归纳法求解 ans += (2 ** m - (m+1)) # for i in dp: # print(i) print(len(A), len(set(A))) return ans if __name__ == '__main__': duixiang = Solution() # a = duixiang.numberOfArithmeticSlices([1,1,1,1,1]) # a = duixiang.numberOfArithmeticSlices([79,20,64,28,67,81,60,58,97,85,92,96,82,89,46,50,15, # 2,36,44,54,2,90,37,7,79,26,40,34,67,64,28,60,89,46, # 31,9,95,43,19,47,64,48,95,80,31,47,19,72,99,28,46, # 13,9,64,4,68,74,50,28,69,94,93,3,80,78,23,80,43,49, # 77,18,68,28,13,61,34,44,80,70,55,85,0,37,93,40,47, # 47,45,23,26,74,45,67,34,20,33,71,48,96]) # a = duixiang.numberOfArithmeticSlices([2,2,-1,2,5,8]) # a = duixiang.numberOfArithmeticSlices([1,2,3,4,5]) # a = duixiang.numberOfArithmeticSlices([6,6,8,10]) a = duixiang.numberOfArithmeticSlices([4,4,3,4,5,6]) # a = duixiang.numberOfArithmeticSlices([3,4,5,6,7]) print(a)