【Leetcode算法题】1218. 最长定差子序列

By Long Luo

今天Leetcode的每日一题是:1218. 最长定差子序列,题目如下:

  1. 最长定差子序列

给你一个整数数组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
18
public 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(N2)O(N^2),其中NN是数组nums\textit{nums}的长度。

  • 空间复杂度:O(1)O(1)

方法二: 动态规划 + 哈希表

思路与算法:

方法一会超时,那么我们需要更好的方法。

我们从左往右遍历arr\textit{arr},并计算出以arr[i]\textit{arr}[i]为结尾的最长的等差子序列的长度,取所有长度的最大值,即为答案。

dp[i]\textit{dp}[i]表示以arr[i]\textit{arr}[i]为结尾的最长的等差子序列的长度,我们可以在arr[i]\textit{arr}[i]左侧找到满足arr[j]=arr[i]d\textit{arr}[j]=\textit{arr}[i]-d的元素,将arr[i]\textit{arr}[i]加到以arr[j]\textit{arr}[j]为结尾的最长的等差子序列的末尾,这样可以递推地从dp[j]dp[j]计算出dp[i]dp[i]

由于我们是从左往右遍历arr\textit{arr}的,对于两个相同的元素,下标较大的元素对应的dp\textit{dp}值不会小于下标较小的元素对应的dp\textit{dp}值,因此下标jj可以取满足j<ij<iarr[j]=arr[i]d\textit{arr}[j]=\textit{arr}[i]-d的所有下标的最大值。故有转移方程

dp[i]=dp[j]+1\textit{dp}[i] = \textit{dp}[j] + 1

由于我们总是在左侧找一个最近的等于arr[i]d\textit{arr}[i]-d元素并取其对应dp\textit{dp}值,因此我们直接用dp[v]\textit{dp}[v]表示以vv为结尾的最长的等差子序列的长度,这样dp[vd]\textit{dp}[v-d]就是我们要找的左侧元素对应的最长的等差子序列的长度,因此转移方程可以改为

dp[v]=dp[vd]+1\textit{dp}[v] = \textit{dp}[v-d] + 1

最后答案为max{dp}\max\{\textit{dp}\}

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
public 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)O(N),其中NN是数组nums\textit{nums}的长度。

  • 空间复杂度:O(N)O(N),哈希表需要O(N)O(N)的空间。