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
29
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(n^2)$。整体复杂度为 $O(n^2)$
  • 空间复杂度：所有哈希表存储的复杂度上界不会超过 $O(n^2)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.446 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。