目錄

?編輯

一，最長定差子序列

1.題目

2，題目接口

?3，解題思路及其代碼

---

一，最長定差子序列

1.題目

給你一個整數(shù)數(shù)組?arr?和一個整數(shù)?difference，請你找出并返回?arr?中最長等差子序列的長度，該子序列中相鄰元素之間的差等于?difference?。

子序列?是指在不改變其余元素順序的情況下，通過刪除一些元素或不刪除任何元素而從?arr?派生出來的序列。

示例 1：

輸入：arr = [1,2,3,4], difference = 1
輸出：4
解釋：最長的等差子序列是 [1,2,3,4]。

示例?2：

輸入：arr = [1,3,5,7], difference = 1
輸出：1
解釋：最長的等差子序列是任意單個元素。

示例 3：

輸入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
輸出：4
解釋：最長的等差子序列是 [7,5,3,1]。

2，題目接口

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {}
};

?3，解題思路及其代碼

1.狀態(tài)轉(zhuǎn)移方程: ? ?

這道題要我們求的是最長定差子序列問題，不再是最長子序列。這里的關(guān)鍵便是定差，也就是說在我們知道差以后我們便可以知道第2個數(shù)的值。我們的dp[i] 表示為以i位置為結(jié)尾的最長等差子序列。

?2.初始化：

?當(dāng)我們的每個nums[i]單獨(dú)構(gòu)成一個子序列時長度為1，所以我們初始化時邊初始化為1即可。

在明確好這些后便可以寫出如下代碼：

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {int n = arr.size();vector<int>dp(n,1);int Maxlenth = 1;for(int i = 0;i<n;i++){int num = arr[i]+difference;//找定差for( int j = i+1;j<n;j++){if(arr[j] == num){dp[j] = dp[i]+1;}}Maxlenth = max(Maxlenth,dp[i]);//每次都要更新一下最大值}return Maxlenth;}
};

但是，這個代碼是過不了的。因為這個代碼的時間復(fù)雜度為O(n^2)。所以我們要對這個代碼做一些優(yōu)化。優(yōu)化的秘訣便是hash表：unordered_map。改進(jìn)思路如下：

1.先創(chuàng)建一個hash表。

2.將arr里面的所有元素和元素的對應(yīng)下標(biāo)放到hash表中構(gòu)成映射，arr[i]作key，下標(biāo)作value。

現(xiàn)在改進(jìn)代碼如下：

class Solution {
public:int longestSubsequence(vector<int>& arr, int difference) {unordered_map<int,int> hash;//在hash表里做dpint n = arr.size();int Max = 1;hash[arr[0]] = 1;for(int i = 1;i<n;i++){hash[arr[i]] = hash[arr[i]-difference]+1;//如果arr[i]-difference那也會訪問最后一個arr[i]-difference的值。因為hash的底層插入是頭插Max = max(Max,hash[arr[i]]);}return Max;}
};

提交：過啦！！！