LC 446. 等差数列划分 II - 子序列
题目描述
这是 LeetCode 上的 446. 等差数列划分 II - 子序列 ,难度为 困难。
给你一个整数数组 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:1
2
3
4
5
6
7
8
9
10
11
12输入: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:1
2
3
4
5输入:nums = [7,7,7,7,7]
输出:16
解释:数组中的任意子序列都是等差子序列。
提示:
- 1 <= nums.length <= 1000
- -$2^{31}$ <= nums[i] <= $2^{31}$ - 1
基本分析
从题目描述来看,我们可以确定这是一个「序列 DP」问题,通常「序列 DP」需要 $O(n^2)$ 的时间复杂度,而某些具有特殊性质的「序列 DP」问题,例如 LIS 问题,能够配合贪心思路 + 二分做到 $O(n\log{n})$ 复杂度。再看一眼数据范围为 $10^3$,基本可以确定这是一道复杂度为 $O(n^2)$ 的「序列 DP」问题。
动态规划 + 容斥原理
既然分析出是序列 DP 问题,我们可以先猜想一个基本的状态定义,看是否能够「不重不漏」的将状态通过转移计算出来。如果不行,我们再考虑引入更多的维度来进行求解。
先从最朴素的猜想出发,定义 $f[i]$ 为考虑下标不超过 $i$ 的所有数,并且以 $nums[i]$ 为结尾的等差序列的个数。
不失一般性的 $f[i]$ 该如何转移,不难发现我们需要枚举 $[0, i - 1]$ 范围内的所有数,假设当前我们枚举到 $[0, i - 1]$ 中的位置 $j$,我们可以直接算出两个位置的差值 $d = nums[i] - nums[j]$,但我们不知道 $f[j]$ 存储的子序列数量是差值为多少的。
同时,根据题目我们要求的是所有的等差序列的个数,而不是求差值为某个具体值 $x$ 的等差序列的个数。换句话说,我们需要记录下所有差值的子序列个数,并求和才是答案。
因此我们的 $f[i]$ 不能是一个数,而应该是一个「集合」,该集合记录下了所有以 $nums[i]$ 为结尾,差值为所有情况的子序列的个数。
我们可以设置 $f[i] = g$,其中 $g$ 为一个「集合」数据结构,我们期望在 $O(1)$ 的复杂度内查的某个差值 $d$ 的子序列个数是多少。
这样 $f[i][j]$ 就代表了以 $nums[i]$ 为结尾,并且差值为 $j$ 的子序列个数是多少。
当我们多引入一维进行这样的状态定义后,我们再分析一下能否「不重不漏」的通过转移计算出所有的动规值。
不失一般性的考虑 $f[i][j]$ 该如何转移,显然序列 DP 问题我们还是要枚举区间 $[0, i - 1]$ 的所有数。
和其他的「序列 DP」问题一样,枚举当前位置前面的所有位置的目的,是为了找到当前位置的数,能够接在哪一个位置的后面,形成序列。
对于本题,枚举区间 $[0, i - 1]$ 的所有数的含义是:枚举以 $nums[i]$ 为子序列结尾时,它的前一个值是什么,也就是 $nums[i]$ 接在哪个数的后面,形成等差子序列。
这样必然是可以「不重不漏」的处理到所有以 $nums[i]$ 为子序列结尾的情况的。
至于具体的状态转移方程,我们令差值 $d = nums[i] - nums[j]$,显然有(先不考虑长度至少为 $3$ 的限制):
含义为:在原本以 $nums[j]$ 为结尾的,且差值为 $d$ 的子序列的基础上接上 $nums[i]$,再加上新的子序列 $(nums[j], nums[i])$,共 $f[j][d] + 1$ 个子序列。
最后对所有的哈希表的「值」对进行累加计数,就是以任意位置为结尾,长度大于 $1$ 的等差子序列的数量 $ans$。
这时候再看一眼数据范围 $-2^{31} <= nums[i] <= 2^{31}-1$,如果从数据范围出发,使用「数组」充当集合的话,我们需要将数组开得很大,必然会爆内存。
但同时有 $1 <= nums.length <= 1000$,也就是说「最小差值」和「最大差值」之间可能相差很大,但是差值的数量是有限的,不会超过 $n^2$ 个。
为了不引入复杂的「离散化」操作,我们可以直接使用「哈希表」来充当「集合」。
每一个 $f[i]$ 为一个哈希表,哈希表的以 {d:cnt}
的形式进行存储,d
为子序列差值,cnt
为子序列数量。
虽然相比使用数组,哈希表常数更大,但是经过上述分析,我们的复杂度为 $O(n^2)$,计算量为 $10^6$,距离计算量上界 $10^7$ 还保有一段距离,因此直接使用哈希表十分安全。
到这里,我们解决了不考虑「长度为至少为 $3$」限制的原问题。
那么需要考虑「长度为至少为 $3$」限制怎么办?
显然,我们计算的 $ans$ 为统计所有的「长度大于 $1$」的等差子序列数量,由于长度必然为正整数,也就是统计的是「长度大于等于 $2$」的等差子序列的数量。
因此,如果我们能够求出长度为 $2$ 的子序列的个数的话,从 $ans$ 中减去,得到的就是「长度为至少为 $3$」子序列的数量。
长度为 $2$ 的等差子序列,由于没有第三个数的差值限制,因此任意的数对 $(j, i)$ 都是一个合法的长度为 $2$ 的等差子序列。
而求长度为 $n$ 的数组的所有数对,其实就是求 首项为 $0$,末项为 $n - 1$,公差为 $1$,长度为 $n$ 的等差数列之和,直接使用「等差数列求和」公式求解即可。
代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class 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(n^2)$。整体复杂度为 $O(n^2)$
- 空间复杂度:所有哈希表存储的复杂度上界不会超过 $O(n^2)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.446
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!