[LeetCode] Longest Harmonious Subsequence 最長和諧子序列

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

Example 1:

Note: The length of the input array will not exceed 20,000.

這道題給了我們一個數組，讓我們找出最長的和諧子序列，關于和諧子序列就是序列中數組的最大最小內插補點均為1。由于這裡隻是讓我們求長度，并不需要傳回具體的子序列。是以我們可以對數組進行排序，那麼實際上我們隻要找出來相差為1的兩個數的總共出現個數就是一個和諧子序列的長度了。明白了這一點，我們就可以建立一個數字和其出現次數之間的映射，利用map的自動排序的特性，那麼我們周遊map的時候就是從小往大開始周遊，我們從第二個映射對開始周遊，每次跟其前面的映射對比較，如果二者的數字剛好差1，那麼就把二個數字的出現的次數相加并更新結果res即可，參見代碼如下：

解法一：

<a>class Solution {</a>

其實我們并不用向上面那種解法那樣用next和prev來移動疊代器，我們周遊每個數字的時候，隻需在map中查找該數字加1是否存在，存在就更新結果res，這樣更簡單一些，參見代碼如下： 

解法二：

參考資料：

<a href="https://discuss.leetcode.com/topic/89990/simple-java-hashmap-solution" target="_blank">https://discuss.leetcode.com/topic/89990/simple-java-hashmap-solution</a>

，如需轉載請自行聯系原部落客。