We define a harmonious array as an array where the difference between its maximum value and its minimum value is exactly 1
.
Given an integer array nums
, return the length of its longest harmonious subsequence among all its possible subsequences.
A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.
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].
Example 2:
Input: nums = [1,2,3,4] Output: 2
Example 3:
Input: nums = [1,1,1,1] Output: 0
Constraints:
1 <= nums.length <= 2 * 104
-109 <= nums[i] <= 109
最长和谐子序列。
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
现在,给你一个整数数组 nums ,请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列,它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-harmonious-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路是hashmap。我需要遍历input数组两次,第一次我用hashmap记录每个数字的出现次数;第二次遍历的时候,对于每一个当前的数字num,如果在hashmap中能找到num + 1就计算长度,否则就跳过。这里我们不需要找num - 1,因为如果两个数字都存在,他们一定都会被计算过,所以无需往两个方向找。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public int findLHS(int[] nums) { 3 HashMap<Integer, Integer> map = new HashMap<>(); 4 for (int num : nums) { 5 map.put(num, map.getOrDefault(num, 0) + 1); 6 } 7 8 int res = 0; 9 for (int num : nums) { 10 if (map.containsKey(num - 1)) { 11 res = Math.max(res, map.get(num) + map.get(num - 1)); 12 } 13 if (map.containsKey(num + 1)) { 14 res = Math.max(res, map.get(num) + map.get(num + 1)); 15 } 16 } 17 return res; 18 } 19 }