[LeetCode][594. 最长和谐子序列] 4种方法：暴力枚举，排序 + 枚举，哈希表
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
23594. 最长和谐子序列
和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是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
方法一：暴力枚举
考虑 \(\textit{nums}\) 中的两个数 \(x\) ，\(y\) ，其下标分别为 \(i\) ，\(j\) ，那么满足数组的和谐子序列只有下列 \(2\) 种情况：
- \(x \leq y \leq x + 1\) ，且 \(|y - x| = 1\) ；
- \(x - 1 \leq y \leq x\) ，且 \(|y - x| = 1\) 。
首先想到的方法是 \(2\) 个循环，分别统计上述情况的最大值并更新，即为答案。
代码如下所示：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
27
28// BF time: O(n^2) space: O(1)
public int findLHS(int[] nums) {
int len = nums.length;
int ans = 0;
for (int i = 0; i < len; i++) {
int minDiff = 0;
int maxDiff = 0;
int cntMin = 0;
int cntMax = 0;
for (int j = 0; j < len; j++) {
if (nums[j] >= nums[i] && nums[j] <= nums[i] + 1) {
minDiff += nums[j] - nums[i];
cntMin++;
}
if (nums[j] >= nums[i] - 1 && nums[j] <= nums[i]) {
maxDiff += nums[j] - nums[i];
cntMax++;
}
}
cntMin = minDiff >= 1 ? cntMin : 0;
cntMax = maxDiff >= 1 ? cntMax : 0;
ans = Math.max(ans, Math.max(cntMin, cntMax));
}
return ans;
}
复杂度分析
- 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
- 空间复杂度：\(O(1)\)，需要常数个空间保存中间变量。
方法二：排序 + 双指针
思路与算法：
方法一中因为需要对 \(2\) 种情况都进行处理，所以代码非常繁琐且耗时，如果先进行排序，从最小值开始计算。
虽然题干说不能修改数字顺序，所以最开始我并没有想到排序，但实际上我们分析可以看出和排序无关，因为最大最小之差为 \(1\)，所以实际结果是和数字顺序无关的。
所以我们可以将数组按照从小到大进行排序，然后依次找到相邻两个连续相同元素的子序列，检查该这两个子序列的元素的之差是否为 \(1\)。
利用滑动窗口的做法，\(\textit{left}\) 指向第一个连续相同元素的子序列的第一个元素，\(\textit{right}\) 指向相邻的第二个连续相同元素的子序列的末尾元素，如果满足二者的元素之差为 \(1\)，则当前的和谐子序列的长度即为两个子序列的长度之和，等于 \(\textit{right} - \textit{left} + 1\)。
代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public 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(N\log N)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。因为需要对数组进行排序，花费的时间复杂度为 \(O(N\log N)\)，然后利用双指针遍历数组花费的时间为 \(O(2N)\)，总的时间复杂度 \(T(N) = O(N\log N) + O(2N) = O(N\log N)\)。
- 空间复杂度：\(O(1)\)，需要常数个空间保存中间变量。