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;
};

參考資料