java数据结构与算法刷题-----LeetCode594. 最长和谐子序列

1. 子序列要尽可能长，并且最大值和最小值之间的差，必须为1。所以这道题的迷惑点在于，最大值最小值之间，可以插入任意个数的元素。
2. 但是只要我们把数字列出来，2,2,2,3,3,3,你会发现，根本不能插入任何其它数字，例如2,2,2,1,3,3,3, 此时的差可不是1，而是3-1=2了。
3. 因此，这道题可以理解为，找数组中两个数，相差为1，并且两个元素的出现次数相加为最多。
4. 法一，hash表：时间复杂度O(n),空间复杂度O(n). 可以使用hash表，记录每个元素的出现次数，如果两个元素相差为1，就记录它们的出现次数，最终返回最大的出现次数。
5. 法二，排序+双指针：时间复杂度O($n\ast lo{g}_{2}N$),空间复杂度O(1). 先对数组排序，然后left指针指向前一个元素，right指针指向后一个元素，如果相差为1，记录它们的长度

法一：hash表

class Solution {public int findLHS(int[] nums) {//hashMap表，key：当前元素值，value：出现次数Map<Integer,Integer> map = new HashMap<>();int res = 0;//最多的出现次数//遍历数组，如果当前元素第一次遇到，直接放入map中，次数置为1//如果不是第一次遇到，获取它已经出现的次数，+1for(int num:nums) map.put(num,map.getOrDefault(num,0)+1);//遍历key值，寻找每个key，在map中是否存在比它大1的key，如果存在，那么他俩可以组成一个子序列//他俩各自的出现次数就是子序列的长度for(int key:map.keySet()){//如果找到了，那么我们只保存最大的子序列长度if(map.containsKey(key + 1)) res = Math.max(res,map.get(key)+map.get(key+1));}return res;}
}

2. 法二：排序+双指针，排序使用快速排序，时间复杂度O($n\ast lo{g}_{2}n$),双指针遍历两遍数组，时间复杂度O(2N), 最终时间复杂度O($n\ast lo{g}_{2}n$)，空间复杂度O(1)。
   

class Solution {public int findLHS(int[] nums) {Arrays.sort(nums);//先对数组排序O(N*log2N)int left = 0, right = 0;//双指针，指向两个相邻的，值不同的元素int cnt = 0, max = 0;//while(right < nums.length){//右指针不能越界//如果left指向的元素，和right指向的元素的差 > 1,left后移while(nums[left] + 1 < nums[right]) left++;//如果left和right所指元素的差，正好差1，说明这两个数组成的序列，满足条件if(nums[right] == nums[left] + 1){//right所指向的元素的后面，如果是重复的值，right右移,直到不重复为止while(right<nums.length && nums[right] == nums[left] + 1) right++;right--;//前移一个，就是最后一个重复的值cnt = right - left + 1;//计算子序列长度max = Math.max(max, cnt);//只保留较大的子序列长度}right++;//右指针不断后移}return max;}
}