【算法挨揍日记】day33——1027. 最长等差数列、446. 等差数列划分 II - 子序列

你的名字 2024-02-17 09:52 49阅读 0赞

## 1027. 最长等差数列 ##

[1027. 最长等差数列][1027.]

### 题目描述： ###

给你一个整数数组 `nums`，返回 `nums` 中最长等差子序列的**长度**。

回想一下，`nums` 的子序列是一个列表 `nums[i1], nums[i2], ..., nums[ik]` ，且 `0 <= i1 < i2 < ... < ik <= nums.length - 1`。并且如果 `seq[i+1] - seq[i]`( `0 <= i < seq.length - 1`) 的值都相同，那么序列 `seq` 是等差的。

![2e79bb45ab144f87acb55c2e66e6c57f.png][]

### 解题思路： ###

算法思路：

1.  状态表⽰：

对于线性  dp  ，我们可以⽤「经验 + 题⽬要求」来定义状态表⽰：

i.  以某个位置为结尾，巴拉巴拉；

ii.  以某个位置为起点，巴拉巴拉。

这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：

dp\[i\]  表⽰：以  i  位置元素为结尾的「所有⼦序列」中，最⻓的等差序列的⻓度。

但是这⾥有⼀个⾮常致命的问题，那就是我们⽆法确定  i  结尾的等差序列的样⼦。这样就会导致

我们⽆法推导状态转移⽅程，因此我们定义的状态表⽰需要能够确定⼀个等差序列。

根据等差序列的特性，我们仅需知道序列⾥⾯的最后两个元素，就可以确定这个序列的样⼦。因

此，我们修改我们的状态表⽰为：

dp\[i\]\[j\]  表⽰：以  i  位置以及  j  位置的元素为结尾的所有的⼦序列中，最⻓的等差序列的

⻓度。规定⼀下  i < j  。

2.  状态转移⽅程：

设  nums\[i\] = b, nums\[j\] = c  ，那么这个序列的前⼀个元素就是  a = 2 \* b - c  。我们

根据  a  的情况讨论：

a.  a  存在，下标为  k  ，并且  a < b  ：此时我们需要以  k  位置以及  i  位置元素为结尾的最

⻓等差序列的⻓度，然后再加上  j  位置的元素即可。于是  dp\[i\]\[j\] = dp\[k\]\[i\] +

1  。这⾥因为会有许多个  k  ，我们仅需离  i  最近的  k  即可。因此任何最⻓的都可以以  k

为结尾；

b.  a  存在，但是  b < a < c  ：此时只能两个元素⾃⼰玩了，  dp\[i\]\[j\] = 2  ；

c.  a  不存在：此时依旧只能两个元素⾃⼰玩了，  dp\[i\]\[j\] = 2  。

综上，状态转移⽅程分情况讨论即可。

优化点：我们发现，在状态转移⽅程中，我们需要确定  a  元素的下标。因此我们可以将所有的元素 +

下标绑定在⼀起，放到哈希表中，这⾥有两种策略：

a.  在  dp  之前，放⼊哈希表中。这是可以的，但是需要将下标形成⼀个数组放进哈希表中。这样

时间复杂度较⾼，我帮⼤家试过了，超时。

b.  ⼀边  dp  ，⼀边保存。这种⽅式，我们仅需保存最近的元素的下标，不⽤保存下标数组。但是

⽤这种⽅法的话，我们在遍历顺序那⾥，先固定倒数第⼆个数，再遍历倒数第⼀个数。这样就

可以在  i  使⽤完时候，将  nums\[i\]  扔到哈希表中。

3.  初始化：

根据实际情况，可以将所有位置初始化为  2  。

4.  填表顺序：

a.  先固定倒数第⼆个数；

b.  然后枚举倒数第⼀个数。

5.  返回值：

由于不知道最⻓的结尾在哪⾥，因此返回  dp  表中的最⼤值。

### 解题代码： ###

class Solution {
    public:
        int longestArithSeqLength(vector<int>& nums) {
            int n=nums.size();
            vector<vector<int>>dp(n,vector<int>(n,2));
            unordered_map<int,int>hash;
            int ret=2;
            hash[nums[0]]=0;
            for(int i=1;i<n-1;i++)
            {
                for(int j=i+1;j<n;j++)
                {
                    int a=2*nums[i]-nums[j];
                    // int k=hash.count(a);
                    if(hash.count(a))
                    {
                        dp[i][j]=dp[hash[a]][i]+1;
                    }
                    ret=max(ret,dp[i][j]);
                }
                    hash[nums[i]]=i;
            }
            return ret;
        }
    };

## 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** 整数。

![4199096b3ab54061afbcd6688996b467.png][]

### 解题思路： ###

算法思路：

1.  状态表⽰：

对于线性  dp  ，我们可以⽤「经验 + 题⽬要求」来定义状态表⽰：

i.  以某个位置为结尾，巴拉巴拉；

ii.  以某个位置为起点，巴拉巴拉。

这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：

dp\[i\]  表⽰：以  i  位置元素为结尾的「所有⼦序列」中，等差⼦序列的个数。

但是这⾥有⼀个⾮常致命的问题，那就是我们⽆法确定  i  结尾的等差序列的样⼦。这样就会导致

我们⽆法推导状态转移⽅程，因此我们定义的状态表⽰需要能够确定⼀个等差序列。

根据等差序列的特性，我们仅需知道序列⾥⾯的最后两个元素，就可以确定这个序列的样⼦。因

此，我们修改我们的状态表⽰为：

dp\[i\]\[j\]  表⽰：以  i  位置以及  j  位置的元素为结尾的所有的⼦序列中，等差⼦序列的个

数。规定⼀下  i < j  。

2.  状态转移⽅程：

设  nums\[i\] = b, nums\[j\] = c  ，那么这个序列的前⼀个元素就是  a = 2 \* b - c  。我们

根据  a  的情况讨论：

a.  a  存在，下标为  k  ，并且  a < b  ：此时我们知道以  k  元素以及  i  元素结尾的等差序列

的个数  dp\[k\]\[i\]  ，在这些⼦序列的后⾯加上  j  位置的元素依旧是等差序列。但是这⾥会多

出来⼀个以  k, i, j  位置的元素组成的新的等差序列，因此  dp\[i\]\[j\] = dp\[k\]\[i\]

\+ 1  ；

b.  因为  a  可能有很多个，我们需要全部累加起来。

综上，  dp\[i\]\[j\] += dp\[k\]\[i\] + 1  。

优化点：我们发现，在状态转移⽅程中，我们需要确定  a  元素的下标。因此我们可以在 dp 之前，将

所有元素 + 下标数组绑定在⼀起，放到哈希表中。这⾥为何要保存下标数组，是因为我们要统计个

数，所有的下标都需要统计。

3.  初始化：

刚开始是没有等差数列的，因此初始化  dp  表为  0  。

4.  填表顺序：

a.  先固定倒数第⼀个数；

b.  然后枚举倒数第⼆个数。

5.  返回值：

我们要统计所有的等差⼦序列，因此返回  dp  表中所有元素的和。

### 解题代码： ###

class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& nums) {
            int n=nums.size();
            vector<vector<int>>dp(n,vector(n,0));
            unordered_map<long long,vector<int>>hash;
            hash[nums[0]].push_back(0);
            int sum=0;
            for(int i=1;i<n-1;i++)
            {
                for(int j=i+1;j<n;j++)
                {
                    long long a=2*(long long)nums[i]-nums[j];
                    if(hash.count(a))
                    {
                        int length=hash[a].size();
                        for(int k=0;k<length;k++)
                        {
                            dp[i][j]+=dp[hash[a][k]][i]+1;
                        }
                    }
                    sum+=dp[i][j];
                }
                hash[nums[i]].push_back(i);
            }
            return sum;
        }
    };

[1027.]: https://leetcode.cn/problems/longest-arithmetic-subsequence/
[2e79bb45ab144f87acb55c2e66e6c57f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/323c2bb22def4cedbd16ca88c1e44491.png
[4199096b3ab54061afbcd6688996b467.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/aab09ac48c694bc9999ce3f31c1282f0.png