🍗[LeetCode]Ar594. 最长和谐子序列【map.put(num, map.getOrDefault(num, 0) 1)】

🚩传送门：https://leetcode-cn.com/problems/longest-harmonious-subsequence/

🍗鸡腿知识点：

1. map.put(num, map.getOrDefault(num, 0) + 1)

题目

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。现在，给你一个整数数组 ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

子序列是由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 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. 我们可以枚举数组中的每一个元素，对于当前枚举的元素 ，它可以和 组成和谐子序列。
2. 再遍历一遍整个数组，找出等于 或 的元素个数，就可以得到以 为最小值的和谐子序列的长度。

复杂度分析

时间复杂度：， 是数组的长度。

空间复杂度：

官方代码

public class Solution {
    public int findLHS(int[] nums) {
        int res = 0;
        //1.i从头遍历到尾巴
        for (int i = 0; i < nums.length; i++) {
            //2.count临时计数
            int count = 0;
            //3.标记是否存在差值,假设[1,1,1]3个数无法构成差值输出 0
            boolean flag = false;
            //4.j查找与i相同元素或者小1的元素
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] == nums[i])
                    count++;
                else if (nums[j] == nums[i]+1) {
                    count++;
                    //5.标记是有差值的
                    flag = true;
                }
            }
            if (flag)
                res = Math.max(count, res);
        }
        return res;
    }
}

👀解题思路：哈希映射 (推荐)

用哈希表（HashMap）来存储每个数出现的次数，这样就能在 的时间内得到 和 出现的次数。

1. 我们首先遍历一遍数组，得到哈希映射。
2. 随后遍历哈希映射，设当前遍历到的键值对为(x, value)，那么我们就查询 在哈希映射中对应的值，就得到了 和 出现的次数。

复杂度分析

时间复杂度：，其中 是数组的长度。

空间复杂度：，用来存储哈希映射。

官方代码

public class Solution {
    public int findLHS(int[] nums) {
        //1.定义Hash表
        HashMap < Integer, Integer > map = new HashMap < > ();
        int res = 0;
        //2.依次遍历数组,存入map
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //3.依次遍历键值对集合
        for (int key: map.keySet()) {
            if (map.containsKey(key + 1))
                res = Math.max(res, map.get(key) + map.get(key + 1));
        }
        return res;
    }
}

解题思路：哈希映射

在方法二中，我们需要对数组进行一次扫描，再对哈希映射进行一次扫描。事实上，我们只需一次扫描就可以。

我们扫描一次数组，当扫描到元素 时，我们首先将 加入哈希映射，随后获取哈希映射中 三者出现的次数 ，那么 即为 组成的和谐子序列的长度， 即为 组成的和谐子序列的长度。

假设数组中最长的和谐子序列的最后一个元素在数组中的位置为 i

那么在扫描到 nums[i] 时，u + v 和 v + w 中一定有一个就是答案。因此这种方法可以找到答案。

复杂度分析

时间复杂度：，其中 是数组的长度。

空间复杂度：，用来存储哈希映射。

官方代码

public class Solution {
    public int findLHS(int[] nums) {
        //1.定义存放的Hashmap
        HashMap < Integer, Integer > map = new HashMap < > ();
        int res = 0;
        //2.遍历数组
        for (int num: nums) {
            //3.将元素存入map,存在取出存放数量,否则 0 
            map.put(num, map.getOrDefault(num, 0) + 1);
            //4.若当前数作为最长序列的结尾,判断是否存在num+1与其组成最长序列
            if (map.containsKey(num + 1))
                res = Math.max(res, map.get(num) + map.get(num + 1));
            //5.若当前数作为最长序列的结尾,判断是否存在num-1与其组成最长序列
            if (map.containsKey(num - 1))
                res = Math.max(res, map.get(num) + map.get(num - 1));
        }
        //6.返回结果
        return res;
    }
}