数组 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。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence
题目分析：像这样的测试用例，[2,2,3,4,5,5]，用遍历的方法需要记录的数：
比如遍历到以三为最后一个元素的数组是否含有等差数列时,虽然此时没有符合条件的等差数列但是应当把这个3之前的元素与3之间的步长（即两元素的差值）都记录下来以备以后使用，
根据需求：需要一个二维数组或者--当然看到二维数组就头疼该给多大的数组，很有可能会不够用，当然，步长（两数的差值）并不会遍历整个整数数轴，所以用hashmap代替即可，python中应该也可使用字典
下面是java代码：
class Solution { public int numberOfArithmeticSlices(int[] A) { HashMap<Integer, Integer>[] diffMaps = new HashMap[A.length]; int res = 0; for(int i = 0;i<A.length;i++){ HashMap<Integer, Integer> diffMap = new HashMap(); diffMaps[i] = diffMap; long num = A[i]; for(int j=0;j<i;j++){ if(num-A[j]>Integer.MAX_VALUE) continue; if(num-A[j]<Integer.MIN_VALUE) continue; int diff = (int)(num-A[j]); int count = diffMaps[j].getOrDefault(diff, 0); diffMaps[i].put(diff,diffMaps[i].getOrDefault(diff, 0)+count+1); res+=count; } } return res; } }
python代码：
#python3 from collections import defaultdict class Solution: def numberOfArithmeticSlices(self,A): dp,ans=[defaultdict(int)],0 #以每个数字作为等差数列最后一项的数组的个数(俩数字也记为1 但是不能加到ans里去) for i,cur in enumerate(A[1:],1): cur_dict=defaultdict(int) for j,prev in enumerate(A[:i]): diff=cur-prev tmp=dp[j][diff] ans+=tmp cur_dict[diff]+=tmp+1 #如上面所说的 俩数字记为1(本质上算不上是等差数列 因为等差数列至少要三项) dp.append(cur_dict) return ans
leetcode 446 等差数列划分 II - 子序列 思路解析
原文：https://www.cnblogs.com/hongdoudou/p/13071522.html