594. Longest Harmonious Subsequence

Leetcode 问题: 594. Longest Harmonious Subsequence
Categories:
Tags:

题目

We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1.

Given an integer array nums, return the length of its longest harmonious subsequence among all its possible subsequences.

A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

传入一 整数阵列 nums，没有排序，找出最长的 Harmonious Subsequence (HS)

Harmonious Subsequence (HS) 是指阵列中最大的值与最小的值相差只差 1

Example

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].
整数阵列 nums 1 3 2 2 5 2 3 7
HS 1 1 2 2 2
HS 2 3 2 2 2 3

上面可以找到有两个 Harmonious Subsequence (HS)，分别是 [1,2,2,2] 跟 [3,2,2,2,3]，其中最长的是 5，所以回传 5

Input: nums = [1,2,3,4]
Output: 2

Input: nums = [1,1,1,1]
Output: 0

演算法

1. 计算所有数字出现的次数

将所有数字出现的次数存到 Map

2. 找所有的 Harmonious Subsequence (HS)

因为 Harmonious Subsequence (HS) 是指阵列中最大的值与最小的值相差只差 1

所以只需要找 每个数字 的下一个 +1 的数字即可

如果有 下一个 +1 数字，表示有 Harmonious Subsequence (HS)

然后将这两个数字的出现次数相加，就可以知道这个数字的 Harmonious Subsequence (HS) 长度是多少

在跟之前最长的 Harmonious Subsequence (HS)比较，留下最长的

答案

JavaScript

function findLHS(numsList) {
    // 数字出现次数对应 Map
    var NumsCountMap = new Map();
    // 计算数字出现次数
    for (var i = 0; i < numsList.length; i++) {
        var currentNumber = numsList[i];
        // 预设数字数量是 1
        var currentNumberCount = 1;
        if (NumsCountMap.has(currentNumber)) {
            // 如果有这个数字对应的数量
            currentNumberCount = NumsCountMap.get(currentNumber);
            // 加上目前的数量
            currentNumberCount++;
        }
        // 设定目前数字出现次数
        NumsCountMap.set(currentNumber, currentNumberCount);
    }
    // 预设最长的 Harmonious Subsequence 是 0
    var longestHarmoniousSubsequenceLength = 0;
    // 检查数字中是否有 Harmonious Subsequence
    NumsCountMap.forEach(function (currentNumberCount, currentNumber) {
        // 目前数字的下一个数字
        var nextCurrentNumber = currentNumber + 1;
        if (NumsCountMap.has(nextCurrentNumber)) {
            // 如果有下一个数字，表示有 Harmonious Subsequence
            // 取得下一个数字出现的次数
            var nextCurrentNumberCount = NumsCountMap.get(nextCurrentNumber);
            // 目前数字的 Harmonious Subsequence 长度
            var currentNumberHarmoniousSubsequenceLength = currentNumberCount + nextCurrentNumberCount;
            // 「目前最长的 Harmonious Subsequence 长度」与「目前数字的 Harmonious Subsequence 长度」取最大的
            longestHarmoniousSubsequenceLength = Math.max(longestHarmoniousSubsequenceLength, currentNumberHarmoniousSubsequenceLength);
        }
    });
    return longestHarmoniousSubsequenceLength;
}

TypeScript

function findLHS(numsList: number[]): number {
    // 数字出现次数对应 Map
    const NumsCountMap = new Map();
    // 计算数字出现次数
    for (let i = 0; i < numsList.length; i++) {
        let currentNumber = numsList[i];
        // 预设数字数量是 1
        let currentNumberCount = 1
        if (NumsCountMap.has(currentNumber)) {
            // 如果有这个数字对应的数量
            currentNumberCount = NumsCountMap.get(currentNumber);
            // 加上目前的数量
            currentNumberCount++;
        }

        // 设定目前数字出现次数
        NumsCountMap.set(currentNumber, currentNumberCount);
    }

    // 预设最长的 Harmonious Subsequence 是 0
    let longestHarmoniousSubsequenceLength = 0;

    // 检查数字中是否有 Harmonious Subsequence
    NumsCountMap.forEach((currentNumberCount: number, currentNumber: number) => {
        // 目前数字的下一个数字
        let nextCurrentNumber = currentNumber + 1;

        if (NumsCountMap.has(nextCurrentNumber)) {
            // 如果有下一个数字，表示有 Harmonious Subsequence
            // 取得下一个数字出现的次数
            let nextCurrentNumberCount =  NumsCountMap.get(nextCurrentNumber);
            // 目前数字的 Harmonious Subsequence 长度
            let currentNumberHarmoniousSubsequenceLength = currentNumberCount + nextCurrentNumberCount;
            // 「目前最长的 Harmonious Subsequence 长度」与「目前数字的 Harmonious Subsequence 长度」取最大的
            longestHarmoniousSubsequenceLength = Math.max(longestHarmoniousSubsequenceLength, currentNumberHarmoniousSubsequenceLength);
        }
    });


    return longestHarmoniousSubsequenceLength;
};

参考资料