最长和谐子序列
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 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
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-harmonious-subsequence
题解一：
先将数组进行排序，然后用类似双指针的方法，一个指针p用for循环从前到后遍历，另一个指针q从0开始，若nums[p]-nums[q]>1,则q一直向前移动直到nums[p]-nums[q]<=1，如果nums[p]-nums[q]=1，则最长和谐子序列的长度就等于max(max,p-q+1)。代码如下：
class Solution {
public int findLHS(int[] nums) {
//对数组进行排序
Arrays.sort(nums);
int count=0;
int max=0;
for(int i=1;i<nums.length;i++){
while(nums[i]-nums[count]>1){
count++;
}
if(nums[i]-nums[count]==1){
max=Math.max(max,i-count+1);
}
}
return max;
}
}题解二：
使用HashMap集合，将数组中元素和元素出现的次数作为键值对存入HashMap集合，然后遍历key，若key+1也在HashMap中，则最长和谐子序列max=max(max,key和key+1对应的value的和)。代码如下：
class Solution {
public int findLHS(int[] nums) {
int max=0;
Map<Integer,Integer> hm=new HashMap<Integer,Integer>();
for(int num:nums){
hm.put(num,hm.getOrDefault(num,0)+1);
}
for(int key:hm.keySet()){
if(hm.containsKey(key+1)){
max=Math.max(max,hm.get(key)+hm.get(key+1));
}
}
return max;
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153954.html
