原文链接: https://leetcode-cn.com/problems/longest-harmonious-subsequence

英文原文

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 ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

 

示例 1：

输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]

示例 2：

输入：nums = [1,2,3,4]
输出：2

示例 3：

输入：nums = [1,1,1,1]
输出：0

 

提示：

• 1 <= nums.length <= 2 * 104
• -109 <= nums[i] <= 109

通过代码

高赞题解

排序 + 滑动窗口

一个直观的想法是，先对 $nums$ 进行排序，然后从前往后使用「双指针」实现「滑动窗口」进行扫描，统计所有符合条件的窗口长度，并在所有长度中取最大值即是答案。

代码：

[]
class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, ans = 0;
        for (int i = 0, j = 0; j < n; j++) {
            while (i < j && nums[j] - nums[i] > 1) i++;
            if (nums[j] - nums[i] == 1) ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }
}

• 时间复杂度：排序的复杂度为 $O(n\log{n})$，通过双指针实现的滑动窗口复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
• 空间复杂度：$O(\log{n})$

---

哈希计数

题目规定的「和谐子序列」中的最值差值正好为 $1$，因而子序列排序后必然符合 $[a,a,..,a+1,a+1]$ 形式，即符合条件的和谐子序列长度为相邻两数（差值为 $1$) 的出现次数之和。

我们可以使用「哈希表」记录所有 $nums[i]$ 的出现次数，然后通过 $O(n)$ 的复杂度找出所有可能的数对（两数差值为 $1$)，并在所有符合条件的数对所能构成的「和谐子序列」长度中取最大值。

代码：

[]
class Solution {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
        int ans = 0;
        for (int i : nums) {
            if (map.containsKey(i - 1)) {
                ans = Math.max(ans, map.get(i) + map.get(i - 1));
            }
        }
        return ans;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

其他「滑动窗口」类型题目

考虑加练如下「滑动窗口」类型题目 🍭🍭🍭

题目	题解	难度	推荐指数
3. 无重复字符的最长子串	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩
30. 串联所有单词的子串	LeetCode 题解链接	困难	🤩🤩
187. 重复的DNA序列	LeetCode 题解链接	中等	🤩🤩🤩🤩
220. 存在重复元素 III	LeetCode 题解链接	中等	🤩🤩🤩
424. 替换后的最长重复字符	LeetCode 题解链接	中等	🤩🤩🤩🤩
480. 滑动窗口中位数	LeetCode 题解链接	困难	🤩🤩🤩🤩
567. 字符串的排列	LeetCode 题解链接	中等	🤩🤩🤩
594. 最长和谐子序列	LeetCode 题解链接	简单	🤩🤩🤩🤩
643. 子数组最大平均数 I	LeetCode 题解链接	简单	🤩🤩🤩🤩🤩
992. K 个不同整数的子数组	LeetCode 题解链接	困难	🤩🤩🤩🤩
1004. 最大连续1的个数 III	LeetCode 题解链接	中等	🤩🤩🤩
1052. 爱生气的书店老板	LeetCode 题解链接	中等	🤩🤩🤩
1208. 尽可能使字符串相等	LeetCode 题解链接	中等	🤩🤩🤩
1423. 可获得的最大点数	LeetCode 题解链接	中等	🤩🤩🤩🤩
1438. 绝对差不超过限制的最长连续子数组	LeetCode 题解链接	中等	🤩🤩🤩
1838. 最高频元素的频数	LeetCode 题解链接	中等	🤩🤩🤩

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
58794	103916	56.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言