No.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：

输入：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
• -231 <= nums[i] <= 231 - 1

思路分析

本题与昨天的题目几乎完全一致。唯一有区别的地方就是将子数组改成了子序列。
但这个改动可不是小小的改动，我们之前的思考在这里几乎不会有什么用处。

子序列是没有连续性的，也就是说，对于任意一些有先后顺序但是没有邻接顺序的数字，只要他们满足差值是一个恒定的数，他们就是合法的等差子序列。

首先要理解题目，才有可能做出来。

那么对于子序列，我们能想到的除了暴力还有别的办法吗？
其实答案很简单，我们只需要去提炼一下规律，一个可以总结的规律。
比如在这一题中，如果我们知道[.....,2,4,6]是一个等差数列，那么4前面的东西有多少位与我们并无关系，也就是说，对于后面的数字来说，我们并不关心2前面有几位，因为都是差为2的等差数列。

那么整个数据结构的雏形就出来了，首先外层是一个从前向后的遍历，每一步都会对自己及之前的东西做一个记录，方便后续使用。
记录的这个东西，肯定是基于等差数列的差来记录的，我们就使用一个HashMap<i32,?>来记录，那么记录的内容是什么呢？
为了后续使用，我们肯定要想记录数量，也就是合法的等差子序列的数量，但是这里又出现了一个问题，长度问题。

长度是一个很关键的点，如果我们记录的是长度为2的，就有可能多算；我们也没有办法只记录长度大于等于3的，因为这必定是基于长度为2的才能推得
在这种情况下，我们使用了HashMap<i32, (i32, i32)>的数据结构。这样可以用前面的i32来记录长度大于等于3的，后面的来记录长度等于2的。

但这里还有一个坑点需要注意，我相信大家也都没发现：

然后我们写出了第一版本的代码

#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn number_of_arithmetic_slices(nums: Vec<i32>) -> i32 {
        use std::collections::*;
        let mut dp: Vec<HashMap<i64, (i32, i32)>> = vec![];
        let n = nums.len();
        let mut res = 0;
        for i in 0..n {
            let mut nxt = HashMap::new();
            for j in 0..i {
                let diff = nums[i] as i64 - nums[j] as i64;
                if let Some(value) = dp[j].get(&diff) {
                    nxt.entry(diff).or_insert((0, 0)).0 += value.0 + value.1;
                    res += value.0 + value.1;
                }
                nxt.entry(diff).or_insert((0, 0)).1 += 1;
            }
            dp.push(nxt);
        }
        res
    }
}
}

dp是一个包含每一个位所有信息的一个总和。 在对nums进行遍历的同时，记录所有数据。

nxt.entry(diff).or_insert((0, 0)).1 += 1;
这句话的意思就是对于所有在i前面的nums[j]都可以与nums[i]组成一个长度为2的组合。所以加到了后面的位。 nxt.entry(diff).or_insert((0, 0)).0 += value.0 + value.1;
这句话的意思是如果j位置之前出现过长度大于3或者长度等于2的，再与nums[i]进行搭配，一定会得到一个长度大于等于3的子序列，那么我们就将其加到前面的位上，并且加到答案上。

这段代码是可以通过的，但是我们发现一个要点。在我们使用(i32, i32)时，总是使用它们的和。代码中出现的只有value[0] + value[1]。那么我们是否可以考虑将其合并？

其实也是可以的。合并之后的含义就变化了，HashMap<i64, i32>表示的就是一个特定的diff下长度大于等于2的所有子序列数量。而最令人震惊的是这好像不影响计算。

Rust代码

#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn number_of_arithmetic_slices(nums: Vec<i32>) -> i32 {
        use std::collections::*;
        let mut dp: Vec<HashMap<i64, i32>> = vec![];
        let n = nums.len();
        let mut res = 0;
        for i in 0..n {
            let mut nxt = HashMap::new();
            for j in 0..i {
                let diff = nums[i] as i64 - nums[j] as i64;
                if let Some(value) = dp[j].get(&diff) {
                    *nxt.entry(diff).or_insert(0) += value;
                    res += value;
                }
                *nxt.entry(diff).or_insert(0) += 1;
            }
            dp.push(nxt);
        }
        res
    }
}
}

看到了吗？其实答案就是我们在读取前一位的长度为2的子序列的时候，加上这一位一定大于等于3了，所以我们多虑了！
但你要是不试你永远也不知道自己多虑了。 😂