[LeetCode][1218. 最长定差子序列] 2种方法:暴力,序列动态规划 + HashMap
By Long Luo
Leetcode 1218. 最长定差子序列 题目如下: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
261218. 最长定差子序列
给你一个整数数组arr和一个整数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]。
提示:
1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4
进阶:你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
方法一:暴力
思路与算法:
首先想到的是暴力法,在第二个循环中寻找构成等差数列的数字并更新长度,找到最大长度。
代码如下所示:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public int longestSubsequence(int[] arr, int difference) {
int len = arr.length;
int ans = 1;
for (int i = 0; i < len; i++) {
int value = arr[i];
int cnt = 1;
for (int j = i + 1; j < len; j++) {
if (arr[j] == value + difference) {
cnt++;
value = arr[j];
}
}
ans = Math.max(ans, cnt);
}
return ans;
}
复杂度分析:
- 时间复杂度:\(O(N^2)\) ,其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度:\(O(1)\)。
方法二:动态规划 + 哈希表
思路与算法:
方法一会超时,那么我们需要更好的方法。
能否使用额外的空间来降低时间复杂度,降到 \(O(N)\) 呢?
从左往右遍历 \(\textit{arr}\),并计算出以 \(\textit{arr}[i]\) 为结尾的最长的等差子序列的长度,更新长度的最大值,即为答案。
令 \(\textit{dp}[i]\) 表示以 \(\textit{arr}[i]\) 为结尾的最长的等差子序列的长度,在 \(\textit{arr}[i]\) 左侧找到满足 \(\textit{arr}[j] =\textit{arr}[i]-d\) 的元素,将 \(\textit{arr}[i]\) 加到以 \(\textit{arr}[j]\) 为结尾的最长的等差子序列的末尾,这样可以递推地从 \(dp[j]\) 计算出 \(dp[i]\)。
由于我们是从左往右遍历 \(\textit{arr}\) 的,对于两个相同的元素,下标较大的元素对应的 \(\textit{dp}\) 值不会小于下标较小的元素对应的 \(\textit{dp}\) 值,因此下标 \(j\) 可以取满足 \(j \lt i\) 且 \(\textit{arr}[j]= \textit{arr}[i] - d\) 的所有下标的最大值。
故转移方程如下:
\[ \textit{dp}[i] = \textit{dp}[j] + 1 \]
由于我们总是在左侧找一个最近的等于 \(\textit{arr}[i] - d\) 元素并取其对应 \(\textit{dp}\) 值,因此我们直接用 \(\textit{dp}[v]\) 表示以 \(v\) 为结尾的最长的等差子序列的长度,这样 \(\textit{dp}[v-d]\) 就是我们要找的左侧元素对应的最长的等差子序列的长度,因此转移方程可以改为
\[ \textit{dp}[v] = \textit{dp}[v-d] + 1 \]
最后答案为 \(\max\{\textit{dp}\}\)。
代码如下所示:1
2
3
4
5
6
7
8
9
10
11public int longestSubsequence(int[] arr, int difference) {
int len = arr.length;
int ans = 1;
Map<Integer, Integer> dp = new HashMap<>();
for (int i = 0; i < len; i++) {
dp.put(arr[i], dp.getOrDefault(arr[i] - difference, 0) + 1);
ans = Math.max(ans, dp.get(arr[i]));
}
return ans;
}
复杂度分析:
- 时间复杂度:\(O(N)\),其中\(N\)是数组 \(\textit{nums}\) 的长度。
- 空间复杂度:\(O(N)\),哈希表需要 \(O(N)\) 的空间。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗