题目描述
这是 LeetCode 上的 446. 等差数列划分 II - 子序列 ，难度为 困难。
Tag : 「动态规划」、「序列 DP」、「容斥原理」、「数学」
给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。
如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。
- 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
- 再例如，[1, 1, 2, 5, 7] 不是等差序列。
数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。
- 例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。
题目数据保证答案是一个 32-bit 整数。
示例 1：
输入：nums = [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] 复制代码
示例 2：
输入：nums = [7,7,7,7,7] 输出：16 解释：数组中的任意子序列都是等差子序列。 复制代码
提示：
- 1 <= nums.length <= 1000
- -2^{31}231 <= nums[i] <= 2^{31}231 - 1
基本分析
从题目描述来看，我们可以确定这是一个「序列 DP」问题，通常「序列 DP」需要 O(n^2)O(n2) 的时间复杂度，而某些具有特殊性质的「序列 DP」问题，例如 LIS 问题，能够配合贪心思路 + 二分做到 O(n\log{n})O(nlogn) 复杂度。再看一眼数据范围为 10^3103，基本可以确定这是一道复杂度为 O(n^2)O(n2) 的「序列 DP」问题。
动态规划 + 容斥原理
既然分析出是序列 DP 问题，我们可以先猜想一个基本的状态定义，看是否能够「不重不漏」的将状态通过转移计算出来。如果不行，我们再考虑引入更多的维度来进行求解。
先从最朴素的猜想出发，定义 f[i]f[i] 为考虑下标不超过 ii 的所有数，并且以 nums[i]nums[i] 为结尾的等差序列的个数。
不失一般性的 f[i]f[i] 该如何转移，不难发现我们需要枚举 [0, i - 1][0,i−1] 范围内的所有数，假设当前我们枚举到 [0, i - 1][0,i−1] 中的位置 jj，我们可以直接算出两个位置的差值 d = nums[i] - nums[j]d=nums[i]−nums[j]，但我们不知道 f[j]f[j] 存储的子序列数量是差值为多少的。
同时，根据题目我们要求的是所有的等差序列的个数，而不是求差值为某个具体值 xx 的等差序列的个数。换句话说，我们需要记录下所有差值的子序列个数，并求和才是答案。
因此我们的 f[i]f[i] 不能是一个数，而应该是一个「集合」，该集合记录下了所有以 nums[i]nums[i] 为结尾，差值为所有情况的子序列的个数。
我们可以设置 f[i] = gf[i]=g，其中 gg 为一个「集合」数据结构，我们期望在 O(1)O(1) 的复杂度内查的某个差值 dd 的子序列个数是多少。
这样 f[i][j]f[i][j] 就代表了以 nums[i]nums[i] 为结尾，并且差值为 jj 的子序列个数是多少。
当我们多引入一维进行这样的状态定义后，我们再分析一下能否「不重不漏」的通过转移计算出所有的动规值。
不失一般性的考虑 f[i][j]f[i][j] 该如何转移，显然序列 DP 问题我们还是要枚举区间 [0, i - 1][0,i−1] 的所有数。
和其他的「序列 DP」问题一样，枚举当前位置前面的所有位置的目的，是为了找到当前位置的数，能够接在哪一个位置的后面，形成序列。
对于本题，枚举区间 [0, i - 1][0,i−1] 的所有数的含义是：枚举以 nums[i]nums[i] 为子序列结尾时，它的前一个值是什么，也就是 nums[i]nums[i] 接在哪个数的后面，形成等差子序列。
这样必然是可以「不重不漏」的处理到所有以 nums[i]nums[i] 为子序列结尾的情况的。
至于具体的状态转移方程，我们令差值 d = nums[i] - nums[j]d=nums[i]−nums[j]，显然有（先不考虑长度至少为 33 的限制）：
f[i][d] = \sum_{j = 0}^{i - 1} (f[j][d] + 1)f[i][d]=j=0∑i−1(f[j][d]+1)
含义为：在原本以 nums[j]nums[j] 为结尾的，且差值为 dd 的子序列的基础上接上 nums[i]nums[i]，再加上新的子序列 (nums[j], nums[i])(nums[j],nums[i])，共 f[j][d] + 1f[j][d]+1 个子序列。
最后对所有的哈希表的「值」对进行累加计数，就是以任意位置为结尾，长度大于 11 的等差子序列的数量 ansans。
这时候再看一眼数据范围 -2^{31} <= nums[i] <= 2^{31}-1−231<=nums[i]<=231−1，如果从数据范围出发，使用「数组」充当集合的话，我们需要将数组开得很大，必然会爆内存。
但同时有 1 <= nums.length <= 10001<=nums.length<=1000，也就是说「最小差值」和「最大差值」之间可能相差很大，但是差值的数量是有限的，不会超过 n^2n2 个。
为了不引入复杂的「离散化」操作，我们可以直接使用「哈希表」来充当「集合」。
每一个 f[i]f[i] 为一个哈希表，哈希表的以 {d:cnt} 的形式进行存储，d 为子序列差值，cnt 为子序列数量。
虽然相比使用数组，哈希表常数更大，但是经过上述分析，我们的复杂度为 O(n^2)O(n2)，计算量为 10^6106，距离计算量上界 10^7107 还保有一段距离，因此直接使用哈希表十分安全。
到这里，我们解决了不考虑「长度为至少为 33」限制的原问题。
那么需要考虑「长度为至少为 33」限制怎么办？
显然，我们计算的 ansans 为统计所有的「长度大于 11」的等差子序列数量，由于长度必然为正整数，也就是统计的是「长度大于等于 22」的等差子序列的数量。
因此，如果我们能够求出长度为 22 的子序列的个数的话，从 ansans 中减去，得到的就是「长度为至少为 33」子序列的数量。
长度为 22 的等差子序列，由于没有第三个数的差值限制，因此任意的数对 (j, i)(j,i) 都是一个合法的长度为 22 的等差子序列。
而求长度为 nn 的数组的所有数对，其实就是求 首项为 00，末项为 n - 1n−1，公差为 11，长度为 nn 的等差数列之和，直接使用「等差数列求和」公式求解即可。
代码：
class Solution { public int numberOfArithmeticSlices(int[] nums) { int n = nums.length; // 每个 f[i] 均为哈希表，哈希表键值对为 {d : cnt} // d : 子序列差值 // cnt : 以 nums[i] 为结尾，且差值为 d 的子序列数量 List<Map<Long, Integer>> f = new ArrayList<>(); for (int i = 0; i < n; i++) { Map<Long, Integer> cur = new HashMap<>(); for (int j = 0; j < i; j++) { Long d = nums[i] * 1L - nums[j]; Map<Long, Integer> prev = f.get(j); int cnt = cur.getOrDefault(d, 0); cnt += prev.getOrDefault(d, 0); cnt ++; cur.put(d, cnt); } f.add(cur); } int ans = 0; for (int i = 0; i < n; i++) { Map<Long, Integer> cur = f.get(i); for (Long key : cur.keySet()) ans += cur.get(key); } int a1 = 0, an = n - 1; int cnt = (a1 + an) * n / 2; return ans - cnt; } } 复制代码
- 时间复杂度：DP 过程的复杂度为 O(n^2)O(n2)，遍历所有的哈希表的复杂度上界不会超过 O(n^2)O(n2)。整体复杂度为 O(n^2)O(n2)
- 空间复杂度：所有哈希表存储的复杂度上界不会超过 O(n^2)O(n2)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.446 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
