594. 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 possible subsequences.

Example 1:

1
2
3
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：

对于subsequence的题目，经常会用到two pointer，一种是从两头像中间靠拢，另一种是前后两个指针按照条件和数字的变化不停的移动。这题就属于后者。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public int findLHS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int res = 0;
        int left = 0, right = 1;
        while (right < nums.length) {
            if (nums[right] - nums[left] > 1) {
                left++;
            } else if (nums[right] - nums[left] < 1) {
                right++;
            } else {
                right++;
                // update the max length of the subarray
                res = Math.max(res, right - left);
            }
        }
        return res;
    }
}