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 23
| 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
|
方法一:暴力枚举
考虑 nums 中的两个数 x ,y ,其下标分别为 i ,j ,那么满足数组的和谐子序列只有下列 2 种情况:
- x≤y≤x+1 ,且 ∣y−x∣=1 ;
- x−1≤y≤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
| 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(N2),其中 N 是数组 nums 的长度。
- 空间复杂度:O(1),需要常数个空间保存中间变量。
方法二:排序 + 双指针
思路与算法:
方法一中因为需要对 2 种情况都进行处理,所以代码非常繁琐且耗时,如果先进行排序,从最小值开始计算。
虽然题干说不能修改数字顺序,所以最开始我并没有想到排序,但实际上我们分析可以看出和排序无关,因为最大最小之差为 1,所以实际结果是和数字顺序无关的。
所以我们可以将数组按照从小到大进行排序,然后依次找到相邻两个连续相同元素的子序列,检查该这两个子序列的元素的之差是否为 1。
利用滑动窗口的做法,left 指向第一个连续相同元素的子序列的第一个元素,right 指向相邻的第二个连续相同元素的子序列的末尾元素,如果满足二者的元素之差为 1,则当前的和谐子序列的长度即为两个子序列的长度之和,等于 right−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),其中 N 是数组 nums 的长度。因为需要对数组进行排序,花费的时间复杂度为 O(NlogN),然后利用双指针遍历数组花费的时间为 O(2N),总的时间复杂度 T(N)=O(NlogN)+O(2N)=O(NlogN)。
-
空间复杂度:O(1),需要常数个空间保存中间变量。
方法三:HashMap
思路与算法:
因为题目要求是统计最大子序列长度,很容易想到使用 HashMap 来统计元素出现次数,首先遍历一次,统计各个元素的多少。
第二次遍历,则再使用第 2 个 HashMap,用于存储之前已出现的数值,然后计算出最长的一个子数列,代码如下所示:
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),其中 N 是数组 nums 的长度。
- 空间复杂度:O(N),其中 N 是数组 nums 的长度,使用了 2 个 HashMap,因此空间复杂度度为 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; }
|
上述代码还存在优化的空间,因为注意到会出现重复的数值,所以我们可以只迭代 HashMap 中的 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),其中 N 是数组 nums 的长度。
- 空间复杂度:O(N),其中 N 是数组 nums 的长度,使用了 1 个 HashMap ,因此空间复杂度度为 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. 😉😃💗