594. Longest Harmonious Subsequence

Problem

We define a harmounious array as 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 possible subsequences.

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.

Problem Summary

A harmonious array refers to an array where the difference between the maximum and minimum elements is exactly 1. Now, given an integer array, you need to find the length of the longest harmonious subsequence among all possible subsequences. Note: The length of the input array will not exceed 20,000.

Solution Approach

• Find such a subarray in the given array: the maximum and minimum values in the subarray must differ by 1. This is an easy problem. First count the frequency of each number, then in the map find the sum of the frequencies of two numbers that differ by 1. Dynamically maintaining the sum of the frequencies of the two numbers gives the maximum length of the subarray required in the end.

Code

package leetcode

func findLHS(nums []int) int {
	if len(nums) < 2 {
		return 0
	}
	res := make(map[int]int, len(nums))
	for _, num := range nums {
		if _, exist := res[num]; exist {
			res[num]++
			continue
		}
		res[num] = 1
	}
	longest := 0
	for k, c := range res {
		if n, exist := res[k+1]; exist {
			if c+n > longest {
				longest = c + n
			}
		}
	}
	return longest
}