【Leetcode算法题】594. 最长和谐子序列

By Long Luo

今天Leetcode的每日一题是:594. 最长和谐子序列,题目如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
594. 最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别 **正好是 `1`** 。
现在,给你一个整数数组 `nums` ,请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列,它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1:
输入:nums = [1,3,2,2,5,2,3,7]
输出:5
解释:最长的和谐子序列是 [3,2,2,2,3]

示例 2:
输入:nums = [1,2,3,4]
输出:2

示例 3:
输入:nums = [1,1,1,1]
输出:0

提示:
1 <= nums.length <= 2 * 10^4
-10^9 <= nums[i] <= 10^9

方法一:HashMap

思路与算法:

首先想到的方法是2个循环,找到最长的子序列。但是没有AC,因为会遇到一个问题,第1个值确定之后,第2个值是比第一个值小1还是大1呢?根据遇到的第一个值,得到的可能不是正确的答案!

于是想到了使用HashMap,首先遍历一次,获取各个元素的多少。第二次遍历,则再使用第2个Map,用于存储之前已出现的数值,然后计算出最长的一个子数列,代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findLHS(int[] nums) {
int len = nums.length;
int ans = 0;
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}

Map<Integer, Integer> has = new HashMap<>();
for (int i = 0; i < len; i++) {
has.put(nums[i], has.getOrDefault(nums[i], 0) + 1);
if (freq.getOrDefault(nums[i] + 1, 0) == 0 && freq.getOrDefault(nums[i] - 1, 0) == 0) {
continue;
}
int plus = freq.get(nums[i]) - has.get(nums[i]) + 1 + freq.getOrDefault(nums[i] + 1, 0) - has.getOrDefault(nums[i] + 1, 0);
int minus = freq.get(nums[i]) - has.get(nums[i]) + 1 + freq.getOrDefault(nums[i] - 1, 0) - has.getOrDefault(nums[i] - 1, 0);
ans = Math.max(ans, Math.max(plus, minus));
}

return ans;
}

复杂度分析:

  • 时间复杂度:O(N)O(N),其中NN是数组nums\textit{nums}的长度。

  • 空间复杂度:O(N)O(N),其中NN是数组nums\textit{nums}的长度,使用了2个HashMap,因此空间复杂度度为O(N)O(N)

方法二:优化HashMap

思路与算法:

分析方法一,我们发现实际上可以存在很多优化空间,第二个HashMap是没有必要的,因为明显是重复计算了,于是我们有了下面的优化代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int findLHS(int[] nums) {
int ans = 0;
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}

for (int x : nums) {
if (freq.getOrDefault(x + 1, 0) == 0 && freq.getOrDefault(x - 1, 0) == 0) {
continue;
}
int plus = freq.get(x) + freq.getOrDefault(x + 1, 0);
int minus = freq.get(x) + freq.getOrDefault(x - 1, 0);
ans = Math.max(ans, Math.max(plus, minus));
}

return ans;
}

上述代码还存在优化的空间,因为注意到会出现重复的数值,所以我们可以只迭代Map中的key值即可,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int findLHS(int[] nums) {
int ans = 0;
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) {
freq.put(x, freq.getOrDefault(x, 0) + 1);
}

for (int key : freq.keySet()) {
if (freq.containsKey(key + 1)) {
int temp = freq.get(key) + freq.get(key + 1);
ans = Math.max(ans, temp);
}
}

return ans;
}

复杂度分析:

  • 时间复杂度:O(N)O(N),其中NN是数组nums\textit{nums}的长度。

  • 空间复杂度:O(N)O(N),其中NN是数组nums\textit{nums}的长度,使用了1个HashMap,因此空间复杂度度为O(N)O(N)

方法三:排序 + 双指针

思路与算法:

虽然题干说不能修改数字顺序,所以最开始我并没有想到排序,但实际上我们分析可以看出和排序无关,因为最大最小之差为11,所以实际是和数字顺序无关的。

所以我们可以将数组按照从小到大进行排序,然后依次找到相邻两个连续相同元素的子序列,检查该这两个子序列的元素的之差是否为11

利用滑动窗口的做法,left\textit{left}指向第一个连续相同元素的子序列的第一个元素,right\textit{right}指向相邻的第二个连续相同元素的子序列的末尾元素,如果满足二者的元素之差为11,则当前的和谐子序列的长度即为两个子序列的长度之和,等于rightleft+1\textit{right} - \textit{left} + 1

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findLHS(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
int left = 0;
int ans = 0;
for (int right = 0; right < len; right++) {
while (nums[right] - nums[left] > 1) {
left++;
}

if (nums[right] - nums[left] == 1) {
ans = Math.max(ans, right - left + 1);
}
}

return ans;
}

复杂度分析:

  • 时间复杂度:O(NlogN)O(N\log N),其中NN是数组nums\textit{nums}的长度。因为需要对数组进行排序,花费的时间复杂度为O(NlogN)O(N\log N),然后利用双指针遍历数组花费的时间为O(2N)O(2N),总的时间复杂度T(N)=O(NlogN)+O(2N)=O(NlogN)T(N) = O(N\log N) + O(2N) = O(N\log N)

  • 空间复杂度:O(1)O(1),需要常数个空间保存中间变量。