和諧子序列的定義

和諧數(shù)組是指一個數(shù)組里元素的最大值和最小值之間的差別正好是1，也就是說我們需要找出比該元素大于或者相等的元素

LeetCode 題目：

給定一個整數(shù)數(shù)組，你需要在所有可能的子序列中找到最長的和諧子序列的長度

題目示例：

輸入: [1,3,2,2,5,2,3,7]
輸出: 5
原因: 最長的和諧數(shù)組是：[3,2,2,2,3].

解法一：暴力枚舉法

暴力枚舉的思想很簡單，也是我們常用的方法，就是雙重遍歷數(shù)組，第一層遍歷是枚舉數(shù)組中的每一個元素并且假設該元素是數(shù)組中最小的元素，第二層遍歷是枚舉元素與該數(shù)組中的每一個元素逐一比較，找出等于枚舉元素或者比枚舉元素大一的元素，統(tǒng)計出最終的元素個數(shù)。

1、解題代碼

/**
 * 使用暴力枚舉的方式
 * 雙重循環(huán)，每次以當前遍歷的元素當作最小元素，然后統(tǒng)計該數(shù)組中比該元素大1的個數(shù)或者相等的元素，最后返回最大的那個數(shù)
 *
 * @param nums 傳入的數(shù)組
 * @return
 */
public static int findLHS(int[] nums) {
    // 記錄最大的和諧子序列長度
    int res = 0;

    // 第一層遍歷，當前元素默認為最小的元素
    for (int i = 0; i < nums.length; i++) {
        // 當前元素最長的子序列長度
        int count = 0;
        // 第二層遍歷，與數(shù)組中的每一個元素進行比較，找出 nums[i]+1 = nums[j] 或者 nums[i]==nums[j] 的元素個數(shù)
        for (int j = 0; j < nums.length; j++) {
            if (nums[i] + 1 == nums[j] || nums[i] == nums[j]) {
                count += 1;
            }
        }
        // 將最大的賦值給res
        res = Math.max(count, res);
    }
    return res;
}

2、復雜度分析

時間復雜度：因為是雙層循環(huán)遍歷，所以時間復雜度是O(N^2)

空間復雜度：在雙層遍歷中，并沒有產生額外的數(shù)組，只是定義了兩個臨時遍歷，所以空間復雜度為O(1)

解法二：兩次遍歷 + HashMap

HashMap + 兩次遍歷的思想也比較簡單，第一次遍歷是統(tǒng)計每個元素出現(xiàn)的次數(shù)，并且將元素的值作為key，出現(xiàn)的次數(shù)作為val 存入到 HashMap 中，第二次遍歷是遍歷 HashMap ，判斷 HashMap 中是否存在比當前key+1的key，如果存在這統(tǒng)計出這兩個key一共出現(xiàn)的次數(shù)，最后返回出現(xiàn)最多的次數(shù)。

1、解題代碼

/**
 * hashMap + 兩次循環(huán)
 * 第一次循環(huán)是統(tǒng)計每個元素出現(xiàn)的個數(shù)
 * 第二次循環(huán)是遍歷HashMap 集合，判斷map集合中是否存在比當前key大于1的key，如果存在就統(tǒng)計兩個key一共出現(xiàn)的次數(shù)
 *
 * @param nums
 * @return
 */
public static int findLHSByHashMap(int[] nums) {
    // 記錄最大的和諧子序列長度
    int res = 0;
    Map<Integer, Integer> hashMap = new HashMap<>();
    // 第一層遍歷，當前元素默認為最小的元素
    for (int i = 0; i < nums.length; i++) {
        hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
    }

    // 遍歷整個map
    for (int key : hashMap.keySet()) {
        if (hashMap.containsKey(key + 1)) {
            res = Math.max(res, hashMap.get(key) + hashMap.get(key + 1));
        }
    }
    return res;
}

2、復雜度分析

時間復雜度：雖然遍歷了兩次，但是沒有出現(xiàn)雙層循環(huán)，所以時間復雜度是O(N)

空間復雜度：這里新增了 HashMap 的對象，所以空間復雜度為O(N)

解法三：單次遍歷 + HashMap

這種方法是前面一種方法的優(yōu)化，將兩次循環(huán)優(yōu)化成一次循環(huán)，可以提升代碼的執(zhí)行效率，思想也比較簡單，就是將元素 X 添加到 Map 集合后，同時判斷出 X 與 X-1 組成的和諧數(shù)組長度和 X 與 X+1 組成的和諧數(shù)組長度，取兩者中最大的一個。

1、解題代碼

/**
 * hashmap+單次遍歷
 * 是一種方法中的改進，在將元素添加到 map 的時候
 * 就計算出計算出元素 X 與 X-1 的和諧數(shù)組的長度和 X 與 X+1 的和諧數(shù)組長度
 * 這種方式雖然時間復雜度跟上一種沒什么區(qū)別，但是可以節(jié)約執(zhí)行時間
 * @param nums
 * @return
 */
public static int findLHSByMap(int[] nums) {
    // 記錄最大的和諧子序列長度
    int res = 0;
    Map<Integer, Integer> hashMap = new HashMap<>();
    // 第一層遍歷，當前元素默認為最小的元素
    for (int i = 0; i < nums.length; i++) {
        hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
        // 判斷是否包含key+1的key
        if (hashMap.containsKey(nums[i] + 1)) {
            res = Math.max(res, hashMap.get(nums[i]) + hashMap.get(nums[i] + 1));
        }
        // 判斷是否包含key-1的key
        if (hashMap.containsKey(nums[i] - 1)) {
            res = Math.max(res, hashMap.get(nums[i]) + hashMap.get(nums[i] - 1));
        }
    }

    return res;
}

2、復雜度分析

時間復雜度：跟上面一樣，時間復雜度是O(N)

空間復雜度：跟上面一樣，空間復雜度為O(N)

最后

歡迎掃碼關注微信公眾號：「平頭哥的技術博文」，和平頭哥一起學習，一起進步。

平頭哥的技術博文