594 Longest Harmonious Subsequence
We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly1.
The longest harmonious subsequence is [3,2,2,2,3].
Note:The length of the input array will not exceed 20,000.
The Idea: The first thing to understand is that if the maximum - minimum value of a subsequence is 1, then that subsequence can only contain values of the maximum and/or minimum since every other number above or below these would break the definition. So for every number in the array, we only need to keep track of a count of two things: a count of the number itself (which will serve as the minimum), and a count of the number greater than itself (which will serve as the maximum). Together, these will make up some subsequence in the input array.
Complexity: O(N) time and space
from collections import Counter
def findLHS(self, nums):
:type nums: List[int]
hist = Counter(nums)
maxx = 0
for key, _ in hist.items():
if key + 1 in hist:
maxx = max(maxx, hist[key] + hist[key + 1])