[LeetCode][1218. 最长定差子序列] 2种方法：暴力，序列动态规划 + HashMap

发表于 更新于 分类于 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 2 分钟

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
26
1218. 最长定差子序列

给你一个整数数组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)。

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

思路与算法：

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

能否使用额外的空间来降低时间复杂度，降到 O(N)O(N) 呢？

从左往右遍历 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 \lt i 且 arr[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[v−d]\textit{dp}[v-d] 就是我们要找的左侧元素对应的最长的等差子序列的长度，因此转移方程可以改为

dp[v]=dp[v−d]+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) 的空间。

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. 😉😃💗