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

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 * 10⁴
-109 <= nums[i] <= 10⁹

来源：力扣（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;
    }
}