LeetCode_哈希表_简单_594.最长和谐子序列

缺乏、安全感 2023-10-06 23:59 2阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是 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 \* 104  
\-109 <= nums\[i\] <= 109

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/longest-harmonious-subsequence

## 2.思路 ##

（1）排序 & 暴力穷举法  
该方法比较容易想到，具体步骤如下：  
① 即先将数组 nums 进行排序，并定义变量 maxLen 来保存最长和谐子序列，其初始值为 0；  
② 枚举所有的子数组，如果当前子数组 nums\[i…j\] 的最大值和最小值的差正好为 1，则更新 maxLen = Math.max(maxLen, j - i + 1)  
③ 遍历结束后，直接返回 maxLen 即可。

> 注意：排序之后所枚举的子数组就可以看作排好序的子序列，而题目只需求解最长和谐子序列的长度，所以排序后的子序列不会影响最终结果。

（2）哈希表  
① 使用 hashMap 记录数组 nums 中的元素以及对应出现的次数，并定义变量 maxLen 来保存最长和谐子序列，其初始值为 0；  
② 遍历 hashMap 中所有的键 num，如果 hashMap 中存在键 num + 1（记 num 和 num + 1 出现的次数依次为 cnt1 和 cnt2），那么**由 cnt1 个 num 和 cnt2 个 num + 1 所组成的子序列正好是一个和谐子序列**，此时更新 maxLen = Math.max(maxLen,cnt1 + cnt2)；  
③ 遍历结束后，直接返回 maxLen 即可。

## 3.代码实现（Java） ##

//思路1————排序 & 暴力穷举法
    class Solution {
        
        public int findLHS(int[] nums) {
        
            Arrays.sort(nums);
            int length = nums.length;
            // maxLen 保存最长和谐子序列，初始值为 0
            int maxLen = 0;
            for (int i = 0; i < length; i++) {
        
                for (int j = i + 1; j < length; j++) {
        
                    if (nums[i] + 1 == nums[j]) {
        
                        maxLen = Math.max(maxLen, j - i + 1);
                    }
                }
            }
            return maxLen;
        }
    }

//思路2————哈希表
    class Solution {
        
        public int findLHS(int[] nums) {
        
    	    // hashMap 记录数组 nums 中的元素以及对应出现的次数
            Map<Integer, Integer> hashMap = new HashMap<>();
            for (int num : nums) {
        
                hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
            }
            // maxLen 保存最长和谐子序列，初始值为 0
            int maxLen = 0;
            for (Integer num : hashMap.keySet()) {
        
                if (hashMap.containsKey(num + 1)) {
        
                    maxLen = Math.max(maxLen, hashMap.get(num) + hashMap.get(num + 1));
                }
            }
            return maxLen;
        }
    }