LeetCode刷题实战594最长和谐子序列

　　算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
　　今天和大家聊的问题叫做 最长和谐子序列，我们先来看题面：
　　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.
　　和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 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
　　解题
　　https://blog.csdn.net/weixin_44560620/article/details/121435593
　　使用map进行计数，key为数组中的元素，value为对应元素出现的次数，首先遍历一次数组，统计出每个元素的出现次数，因为和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1，而和谐子序列就是在这个基础上 通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。因此我们可以发现我们不需要关心最大值和最小值出现的先后顺序，我们只关心最大值和最小值出现的总次数，又因为最大值和最小值之间的差值刚好为1，因此和谐子序列只由两个元素组成，他们的差值为1，因此我们可以遍历map，枚举所有差值为1的二元组，找出出现总次数最多的二元组，就是最长的和谐子序列class Solution {
　　public:
　　int findLHS(vector &nums) {
　　map m;
　　int res(0);
　　for (int i = 0; i < nums.size; ++i) {
　　m[nums[i]]=m.count(nums[i])?m[nums[i]]+1:1;
　　}
　　for (auto item:m){
　　if (m.count(item.first+1))
　　{
　　res=max(res,item.second+m[item.first+1]);
　　}
　　}
　　return res;
　　}
　　};
　　上期推文：
　　LeetCode1-580题汇总，希望对你有点帮助！
　　LeetCode刷题实战581：最短无序连续子数组
　　LeetCode刷题实战582：杀掉进程
　　LeetCode刷题实战583：两个字符串的删除操作
　　LeetCode刷题实战584：寻找用户推荐人
　　LeetCode刷题实战585：2016年的投资
　　LeetCode刷题实战586：订单最多的客户
　　LeetCode刷题实战587：安装栅栏
　　LeetCode刷题实战588：设计内存文件系统
　　LeetCode刷题实战589：N 叉树的前序遍历
　　LeetCode刷题实战590：N 叉树的后序遍历
　　LeetCode刷题实战591：标签验证器
　　LeetCode刷题实战592：分数加减运算
　　LeetCode刷题实战593：有效的正方形