当前位置:首页 » 《随便一记》 » 正文

LeetCode 594 最长和谐子序列[双指针Map] HERODING的LeetCode之路_HERODING23的博客

0 人参与  2022年06月01日 13:42  分类 : 《随便一记》  评论

点击全文阅读


在这里插入图片描述
解题思路:
既然可以删除元素,那么所谓的不改变顺序这个条件就是幌子,直接sort排序,用双指针的思想,或者说滑动窗口的思想,begin固定最小值,i不断往后遍历,作为最大值的下标,一旦不满足条件,begin++,满足条件更新最大长度,代码如下:

class Solution {
public:
    int findLHS(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int begin = 0;
        int res = 0;
        for(int i = 0; i < nums.size(); i ++) {
            while(nums[i] - nums[begin] > 1) {
                begin ++;
            }
            if(nums[i] - nums[begin] == 1) {
                res = max(res, i - begin + 1);
            }
        }
        return res;
    }
};

时间复杂度:O(NlogN)
空间复杂度:O(1)

当然还有更简单的实现,利用map,直接实现映射,观察前后两个差为1的数的个数之和,找到最大的返回即可,代码如下:

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> mp;
        int res = 0;
        for(auto& num : nums) {
            mp[num] ++;
        }
        for(auto& [a, b] : mp) {
            if(mp.count(a + 1)) {
                res = max(res, b + mp[a + 1]);
            }
        }
        return res;
    }
};

时间复杂度:O(N)
空间复杂度:O(N)


点击全文阅读


本文链接:http://zhangshiyu.com/post/41168.html

复杂度  条件  思想  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 她的记忆停留在了最爱初恋的那年许欣柔楚临川完本_她的记忆停留在了最爱初恋的那年(许欣柔楚临川)
  • 全书浏览假千金的实习生男友霸占我办公室,我反手让他们倾家荡产(顾家明)_假千金的实习生男友霸占我办公室,我反手让他们倾家荡产(顾家明)全书结局
  • 童养夫让我给他的新欢出修复费(林嘉芝林思雅)_童养夫让我给他的新欢出修复费林嘉芝林思雅
  • 全文资助生女婿让我给他白月光付三千万月子中心钱(宋清玉宋雅)列表_全文资助生女婿让我给他白月光付三千万月子中心钱
  • 碎在时光里的谎言喻景宴秦明月完本_碎在时光里的谎言(喻景宴秦明月)
  • 旧爱剜心吻成灰席鄢之岑秋全书免费旧爱剜心吻成灰席鄢之岑秋全书免费
  • 结婚六年丈夫不碰我谁知儿子亲爹是寡头(纪清言傅司砚),结婚六年丈夫不碰我谁知儿子亲爹是寡头
  • 老公想换掉我的男胎,我笑他自不量力(宋薇于继业)_老公想换掉我的男胎,我笑他自不量力宋薇于继业
  • 给太子下了噬心蛊后,皇后找上门(小夭赵劼)全书浏览_给太子下了噬心蛊后,皇后找上门全书浏览
  • 豪门绝嗣!带球跑的夫人回来了!(谢长宴慕清杳)_豪门绝嗣!带球跑的夫人回来了!谢长宴慕清杳
  • 完美身材(李朵林之晴)_完美身材李朵林之晴
  • 离婚后,我和快穿系统绑定(白意秋陈荣周立慧)_离婚后,我和快穿系统绑定(白意秋陈荣周立慧)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1