leetcode-594-Longest Harmonious Subsequence

chenjx85

发布于 2018-05-22 16:39:29

4040

发布于 2018-05-22 16:39:29

题目描述：

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Note: The length of the input array will not exceed 20,000.

要完成的函数：

int findLHS(vector<int>& nums)

说明：

最大值和最小值相差1，vector里面的数值又都是整数，所以我们要找的子数组只能包含最大值和最小值，不能有其他中间值。

所以我们找1有几个，跟1相差1的（这里我们找同方向的数）即2，有多少个。2有几个，跟2相差1的（依然同个方向）即3，有多少个。

最终统计完，我们就可以知道最长的子数组有多少个元素了。

遍历一遍vector，我们可以用map来存储数值的个数。

然后再遍历一遍map，按照上述方法统计各个子数组的长度，记录最长的长度。

代码如下：

    int findLHS(vector<int>& nums) 
    {
        unordered_map<int,int>m1;//采用unordered_map更快
        for(int i=0;i<nums.size();i++)//存储各种数字的个数
        {
            if(!m1.count(nums[i]))
                m1[nums[i]]=1;
            else
                m1[nums[i]]++;
        }
        int max1=0;
        for(unordered_map<int,int>::iterator iter=m1.begin();iter!=m1.end();iter++)
        {
            if(m1.count(iter->first+1))//如果存在大1的数
            {
                max1=max(max1,m1[iter->first+1]+iter->second);
            }
        }
        return max1;
    }

上述代码简洁，实测93ms，beats 74.88% of cpp submissions。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-05-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度