【LeetCode】最长和谐子序列 Java 题解

2021 年 11 月 20 日
本文字数：787 字
阅读完需：约 3 分钟

题目描述

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是 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
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/longest-harmonious-subsequence著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法每日一题是求最长和谐子序列题目，一看到子序列就容易联想到 DP 解决思路，但是这个题目却不需要 DP。仔细阅读分析题目**和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是 1 **。这个条件，差值是 1，限制了元素必须相邻。我们采用 hashmap 存储结构，遍历数组,记录每一个元素出现的次数，然后通过 hashmap 求相邻的元素出现的次数，两者的和即位子序列的长度，具体实现代码如下：

通过代码

class Solution {    public int findLHS(int[] nums) {        HashMap <Integer, Integer> map = new HashMap <>();        int ans = 0;        for (int num : nums) {            map.put(num, map.getOrDefault(num, 0) + 1);        }        for (int key : map.keySet()) {            if (map.containsKey(key + 1)) {                ans = Math.max(ans, map.get(key) + map.get(key + 1));            }        }        return ans;    }}