leetcode-594-Longest Harmonious Subsequence

题目描述:

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。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

Python函数默认值参数的2个坑

在定义函数时,Python支持默认值参数,在定义函数时可以为形参设置默认值。在调用带有默认值参数的函数时,可以不用为设置了默认值的形参进行传值,此时函数将会直接...

2866
来自专栏java一日一条

JavaScript 中对象的深拷贝

在JavaScript中,对对象进行拷贝的场景比较常见。但是简单的复制语句只能对对象进行浅拷贝,即复制的是一份引用,而不是它所引用的对象。而更多的时候,我们希望...

912
来自专栏有趣的Python

代码模板:python-基础-2(条件语句)

2 条件语句 在写代码的时候, 往往需要根据某些条件进行判断,并根据判断结果执行不同的分支代码。 2.1 if 语句 elif else c = 1 if c...

2846
来自专栏破晓之歌

如何创建对象以及jQuery中创建对象的方式(推荐)

在实际使用当中,字面量创建对象虽然很有用,但是它并不能满足我们的所有需求,我们希望能够能够和其他后台语言一样创建一个类,然后声明类的实例就能够多次使用,而不用每...

1192
来自专栏C/C++基础

C++学习知识点

答:多态:同一操作作用于不同的对象,可以有不同的解释,产生不同的执行结果。在运行时,可以通过指向基类的指针,来调用实现派生类中的方法。 C++中,实现多态有...

742
来自专栏锦小年的博客

python学习笔记7.3-内建模块collections

Python的内建模块collections为我们提供了一系列的优化操作,本质上就是元组、字典、集合、列表的特殊功能版。 1. namedtuple name...

2195
来自专栏编程

PYTHON数据类型

Python3 中有六个标准的数据类型: Number(数字) String(字符串) List(列表) Tuple(元组) Sets(集合) Dictiona...

2036
来自专栏Vamei实验室

Java基础01 从HelloWorld到面向对象

Java是完全面向对象的语言。Java通过虚拟机的运行机制,实现“跨平台”的理念。我在这里想要呈现一个适合初学者的教程,希望对大家有用。 "Hello Worl...

1876
来自专栏我和我大前端的故事

啊,函数呐!!!

一份需要你补充完整的函数导图!我还是一个初学者,这篇文章是我所知道的所有关于函数的知识,如有不完善或者错误,希望能够在评论下方指出,哈哈哈,大神勿喷。

842
来自专栏python3

python 内置函数

基本的数据操作基本都是一些数学运算(当然除了加减乘除)、逻辑操作、集合操作、基本IO操作,然后就是对于语言自身的反射操作,还有就是字符串操作。

1042

扫码关注云+社区

领取腾讯云代金券