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.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possiblesubsequences.

Example 1:

Input:
 [1,3,2,2,5,2,3,7]

Output:
 5

Explanation:
 The longest harmonious subsequence is [3,2,2,2,3].

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

1. Just convert input array into a dictionary of elements.

2. For each element in the dictionary, check if the next element exists, for ex: if dict contains key '2', check if there is a '3' in there.If yes, then find the length of that subsequence using sum of no of elements of each type; If not, proceed to next element

3. Return the max

这道题给了我们一个数组，让我们找出最长的和谐子序列，关于和谐子序列就是序列中数组的最大最小差值均为1。由于这里只是让我们求长度，并不需要返回具体的子序列。所以我们可以对数组进行排序，那么实际上我们只要找出来相差为1的两个数的总共出现个数就是一个和谐子序列的长度了。明白了这一点，我们就可以建立一个数字和其出现次数之间的映射，然后再遍历每个数字的时候，只需在 HashMap 中查找该数字加1是否存在，存在就更新结果 res(不需要排序)

class Solution(object):
    def findLHS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        hashmap = collections.Counter(nums)
        result = 0
        for i in hashmap:
            if i+1 in hashmap:
                result = max(result, hashmap[i]+hashmap[i+1])
        return result