LeetCode——594. 最长和谐子序列(Longest Harmonious Subsequence)[简单]——分析及代码(C++)
2021/11/21 1:10:02
本文主要是介绍LeetCode——594. 最长和谐子序列(Longest Harmonious Subsequence)[简单]——分析及代码(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
LeetCode——594. 最长和谐子序列[Longest Harmonious Subsequence][简单]——分析及代码[C++]
- 一、题目
- 二、分析及代码
- 1. 哈希表
- (1)思路
- (2)代码
- (3)结果
- 三、其他
一、题目
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 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 * 10^4
- -10^9 <= nums[i] <= 10^9
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-harmonious-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、分析及代码
1. 哈希表
(1)思路
结合哈希表统计每个元素出现的次数,则差值为 1 的 2 个元素的最大总出现次数就是最长和谐子序列的长度。
(2)代码
class Solution { public: int findLHS(vector<int>& nums) { unordered_map<int, int> cnt;//哈希表,记录各元素出现次数 for (int num : nums) { cnt[num]++; } int ans = 0;//最长和谐子序列的长度 for (auto [key, val] : cnt) {//遍历出现过的元素 if (cnt.count(key + 1) != 0) {//和谐数组中最大值和最小值差别必须为1 ans = max(ans, val + cnt[key + 1]);//更新最大长度 } } return ans; } };
(3)结果
执行用时 :52 ms,在所有 C++ 提交中击败了 95.76% 的用户;
内存消耗 :39 MB,在所有 C++ 提交中击败了 62.00% 的用户。
三、其他
暂无。
这篇关于LeetCode——594. 最长和谐子序列(Longest Harmonious Subsequence)[简单]——分析及代码(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享