Sliding window
Longest Harmonious Subsequence
A harmonious array is defined as an array where the difference between the maximum and minimum values is exactly 1.
Given an integer array nums, your task is to return the length of its longest harmonious subsequence. A subsequence is a sequence that can be derived from the array by deleting some or no elements, while maintaining the order of the remaining elements.
Examples
Example 1:
- Input:
nums = [1, 3, 2, 2, 5, 2, 3, 7] - Output:
5 - Explanation: The longest harmonious subsequence is
[3, 2, 2, 2, 3].
- Input:
Example 2:
- Input:
nums = [1, 2, 3, 4] - Output:
2 - Explanation: The longest harmonious subsequence is
[1, 2]or[2, 3].
- Input:
Example 3:
- Input:
nums = [1, 1, 1, 1] - Output:
0 - Explanation: There are no two different values, so no harmonious subsequence exists.
- Input:
int difference = 0;
int left= 0;
int maxLength = 0;
public int findLHS(int[] nums) {
// Sort the array
Arrays.sort(nums);
int left = 0; // Left pointer for the sliding window
int maxLength = 0; // To store the maximum length of harmonious subsequence
// Right pointer will iterate through the array
for (int right = 0; right < nums.length; right++) {
// Adjust the left pointer to make sure the difference is <= 1
while (nums[right] - nums[left] > 1) {
left++;
}
// If the difference is exactly 1, calculate the current length of the subsequence
if (nums[right] - nums[left] == 1) {
maxLength = Math.max(maxLength, right - left + 1);
}
}
return maxLength;
}
