最长和谐子序列

力扣 594. 最长和谐子序列

题目说明

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是 1 。

现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

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

提示：

1 <= nums.length <= 2 * 10^4
-10^9 <= nums[i] <= 10^9

示例

示例 1:

1
2
3

输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]

示例 2:

1 2	输入：nums = [1,2,3,4] 输出：2

示例 3:

1 2	输入：nums = [1,1,1,1] 输出：0

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现因为本题不要求是子数组，所以可以直接对元素进行统计，让我们来看看具体如何实现的吧。

实现

class Solution {
    /**
     * 数组
     * HashMap
     */
    public int findLHS(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();

        // 记录每个元素出现的频次
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        int result = 0;

        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();

            int sub = map.getOrDefault(key - 1, -1);
            int add = map.getOrDefault(key + 1, -1);

            // 加一减一的数都没出现过就跳过
            if (sub == -1 && add == -1) {
                continue;
            }
            result = Math.max(result, value + Math.max(sub, add));
        }

        return result;
    }
}