LeetCode 594——最长和谐子序列

序列"/>

LeetCode 594——最长和谐子序列

一、题目介绍

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。

示例 1:

输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].
说明: 输入的数组长度最大不超过20,000.

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题思路

（1）哈希映射方法：确定每个元素x在数组出现过的次数保存在map中，再遍历数组nums，记录x和x+1在数组中出现的次数即为和谐数组的长度。

（2）双指针方法：首先给数组排序，然后利用双指针的特性进行比较和统计。

三、解题代码

（1）哈希映射方法：
int findLHS(vector<int>& nums) {map<int,int> mp;//记录每个值出现的次数for(int i =0; i < nums.size(); ++i){mp[nums[i]]++;}int res = 0;//设当前数为x，只需找到当前数组中x和x+1的个数，这些元素组成的即为和谐数组for(int i = 0; i < nums.size(); i++){if(mp[nums[i]+1])res = max(res, mp[nums[i]]+mp[nums[i]+1]); //记录最长的和谐数组的长度}return res;}（2）双指针方法：
int findLHS(vector<int>& nums) {sort(nums.begin(), nums.end()); int l = 0, res = 0;for(int j = 0; j < nums.size(); ++j){while(nums[j] - nums[l] > 1) //前后元素之差大于1l++;if(nums[j] - nums[l] == 1)  //前后元素之差恰好等于1res = max(res, j-l+1);}return res;}

四、解题结果