(LeetCode 每日一题) 594. 最长和谐子序列 (哈希表)

思路：哈希表，时间复杂度0(n)。
用哈希表mp来记录每个元素值出现的次数，然后枚举所有值x，看其x+1是否存在，存在的话就可以维护最长的子序列长度mx。

C++版本：

class Solution {
public:int findLHS(vector<int>& nums) {unordered_map<int,int> mp;for(auto x:nums){mp[x]++;}int mx=0;for(auto x:mp){if(mp.contains(x.first+1)!=0){cout<<x.first<<" :" <<x.second<<endl;mx=max(mx,x.second+mp[x.first+1]);}}return mx;}
};

JAVA版本：

class Solution {public int findLHS(int[] nums) {Map<Integer,Integer> mp=new HashMap<>();for(var x:nums){mp.merge(x,1,Integer::sum);}int mx=0;for(var x:nums){int t=mp.getOrDefault(x+1,0);if(t==0) continue;mx=Math.max(mx,mp.get(x)+mp.get(x+1));}return mx;}
}

Go版本：

func findLHS(nums []int) int {mp:=map[int]int{}for _,x:=range nums {mp[x]++}mx:=0for key,val:=range mp {if mp[key+1]!=0 {mx=max(mx,val+mp[key+1])}}return mx
}