446-等差数列划分 II - 子序列(Arithmetic Slices II - Subsequence)

原文链接: https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence

英文原文

Given an integer array nums, return the number of all the arithmetic subsequences of nums.

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, [1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are arithmetic sequences.
For example, [1, 1, 2, 5, 7] is not an arithmetic sequence.

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

The test cases are generated so that the answer fits in 32-bit integer.

Example 1:

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[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]

Example 2:

Input: nums = [7,7,7,7,7]
Output: 16
Explanation: Any subsequence of this array is arithmetic.

Constraints:

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1

中文题目

给你一个整数数组 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³¹ <= nums[i] <= 2³¹ - 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$ 的限制）：

$$
f[i][d] = \sum_{j = 0}^{i - 1} (f[j][d] + 1)
$$

含义为：在原本以 $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$ 的等差数列之和，直接使用「等差数列求和」公式求解即可。

代码：

[]
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)$

其他「序列 DP」问题

题目	题解	难度	推荐指数
354. 俄罗斯套娃信封问题	LeetCode 题解链接	困难	🤩🤩🤩🤩🤩
368. 最大整除子集	LeetCode 题解链接	中等	🤩🤩🤩🤩
446. 等差数列划分 II - 子序列	LeetCode 题解链接	困难	🤩🤩🤩🤩🤩
740. 删除并获得点数	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩
978. 最长湍流子数组	LeetCode 题解链接	中等	🤩🤩🤩
1035. 不相交的线	LeetCode 题解链接	中等	🤩🤩🤩🤩
1143. 最长公共子序列	LeetCode 题解链接	中等	🤩🤩🤩🤩
1713. 得到子序列的最少操作次数	LeetCode 题解链接	困难	🤩🤩🤩🤩🤩

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或加入「组队打卡」小群，提供写「证明」&「思路」的高质量题解。

所有题解已经加入刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
19663	35717	55.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
等差数列划分	中等

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途