前言說明

算法學(xué)習(xí)，日常刷題記錄。

題目連接

最長和諧子序列

題目內(nèi)容

和諧數(shù)組是指一個數(shù)組里元素的最大值和最小值之間的差別正好是1。

現(xiàn)在，給你一個整數(shù)數(shù)組nums，請你在所有可能的子序列中找到最長的和諧子序列的長度。

數(shù)組的子序列是一個由數(shù)組派生出來的序列，它可以通過刪除一些元素或不刪除元素、且不改變其余元素的順序而得到。

示例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 <= nums.length <= 2 * 10^4

-10^9 <= nums[i] <= 10^9

分析過程

思路：哈希表法。

第一步

定義集合map，保存數(shù)組中每個數(shù)字出現(xiàn)的次數(shù)。

第二步

遍歷數(shù)組nums，統(tǒng)計數(shù)組中每個數(shù)字出現(xiàn)的次數(shù)，用集合map的getOrDefault方法。

第三步

定義最長的和諧子序列的長度maxLength，遍歷集合map中的key，即尋找以key作為最小值的子序列。

每次遍歷時：

集合map尋找是否存在比當(dāng)前key大1的key，因為和諧子序列是最大值和最小值的差正好是1，若存在，那么當(dāng)前和諧子序列的長度是key的次數(shù)和key+1的次數(shù)之和，而子序列不一定連續(xù)，所以任意兩個最大值和最小值都可以去構(gòu)造出和諧子序列，然后比較兩者的值，取較大值賦給最長的和諧子序列的長度maxLength。

例如：nums = [1,3,2,2,5,2,3,7]

那么，1有1個，3有2個，2有3個，5有1個，7有1個。

當(dāng)key為1時，尋找2，1和2組合成和諧子序列，把其他多余的數(shù)去掉，此序列的長度就是1的個數(shù)和2的個數(shù)，即1+3=4。

當(dāng)key為3時，尋找4，3和4組合成和諧子序列，把其他多余的數(shù)去掉，此序列的長度就是3的個數(shù)和4的個數(shù)，因為沒有4，所以不存在和諧子序列。

當(dāng)key為2時，尋找3，2和3組合成和諧子序列，把其他多余的數(shù)去掉，此序列的長度就是2的個數(shù)和3的個數(shù)，即3+2=5。

當(dāng)key為5時，尋找6，5和6組合成和諧子序列，把其他多余的數(shù)去掉，此序列的長度就是5的個數(shù)和6的個數(shù)，因為沒有6，所以不存在和諧子序列。

當(dāng)key為7時，尋找8，7和8組合成和諧子序列，把其他多余的數(shù)去掉，此序列的長度就是7的個數(shù)和8的個數(shù)，因為沒有8，所以不存在和諧子序列。

所以綜上所述，和諧子序列長度分別為4和5，最大和諧子序列為5。

第四步

遍歷集合map結(jié)束后，返回最長的和諧子序列的長度maxLength。

解答代碼

class Solution {
    public int findLHS(int[] nums) {
        // 哈希表法

        // 定義集合map，保存數(shù)組中每個數(shù)字出現(xiàn)的次數(shù)
        Map<Integer, Integer> map = new HashMap<>();

        // 遍歷數(shù)組，統(tǒng)計數(shù)組中每個數(shù)字出現(xiàn)的次數(shù)
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 定義最長的和諧子序列的長度
        int maxLength = 0;

        // 遍歷集合map中的key
        for (int key : map.keySet()) {
            // 尋找是否存在比當(dāng)前key大1的key，因為和諧子序列是最大值和最小值的差正好是1
            if (map.containsKey(key + 1)) {
                // 當(dāng)前和諧子序列的長度是key的次數(shù)和key+1的次數(shù)之和，因為子序列不一定連續(xù)，所以任意兩個最大值和最小值都可以去構(gòu)造出和諧子序列
                maxLength = Math.max(maxLength, map.get(key) + map.get(key + 1));
            }
        }

        // 返回最長的和諧子序列的長度
        return maxLength;
    }
}

提交結(jié)果

執(zhí)行用時15ms，時間擊敗67.21%的用戶，內(nèi)存消耗39.4MB，空間擊敗45.61%的用戶。

運行結(jié)果

原文鏈接

原文鏈接：最長和諧子序列