最长和谐子序列
难度:
标签:
题目描述
We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1.
Given an integer array nums, return the length of its longest harmonious subsequence among all its possible subsequences.
A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [1,3,2,2,5,2,3,7] Output: 5 Explanation: The longest harmonious subsequence is [3,2,2,2,3].
Example 2:
Input: nums = [1,2,3,4] Output: 2
Example 3:
Input: nums = [1,1,1,1] Output: 0
Constraints:
1 <= nums.length <= 2 * 104-109 <= nums[i] <= 109
代码结果
运行时间: 240 ms, 内存: 17.8 MB
// 思路：
// 1. 使用Java Streams来构建一个哈希映射，记录每个数字的出现次数。
// 2. 使用Streams来遍历哈希映射，并寻找最长的和谐子序列长度。
// 3. 返回最大的和谐子序列长度。
import java.util.*;
import java.util.stream.*;
public class HarmoniousArrayStream {
public int findLHS(int[] nums) {
Map<Integer, Long> map = Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(e -> e, Collectors.counting()));
return map.keySet().stream()
.filter(key -> map.containsKey(key + 1))
.mapToInt(key -> (int) (map.get(key) + map.get(key + 1)))
.max()
.orElse(0);
}
public static void main(String[] args) {
HarmoniousArrayStream has = new HarmoniousArrayStream();
int[] nums = {1, 3, 2, 2, 5, 2, 3, 7};
System.out.println(has.findLHS(nums)); // 输出：5
}
}解释
方法:
这个题解使用了哈希表的思路。首先用 Counter 统计数组中每个数字出现的次数，然后遍历哈希表中的每个键值对。对于每个键 key，如果 key+1 也在哈希表中，就计算 key 和 key+1 出现次数之和，并更新结果 ret 为 ret 和这个和中较大的那个。最后返回 ret 即可。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么选择使用哈希表来解决这个问题？哈希表在这里具体起到了什么作用？
▷🦆
在题解中，为什么只检查了key+1在哈希表中的存在，而没有考虑key-1的情况？
▷🦆
如果哈希表中的键值对非常多，是否会影响算法的性能？具体来说，这种影响体现在哪些方面？
▷