LeetCode 525. 连续数组(前缀和+哈希)
发布日期:2021-07-01 03:25:42
浏览次数:3
分类:技术文章
本文共 781 字,大约阅读时间需要 2 分钟。
1. 题目
给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组(的长度)。
示例 1:输入: [0,1]输出: 2说明: [0, 1] 是具有相同数量0和1的最长连续子数组。示例 2:输入: [0,1,0]输出: 2说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/contiguous-array著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
类似题目:
- 把0看成-1,找和为0的最长长度,跟560题差不多
- 记录前缀和,第一次出现时,存入map,记录下标
- 第二次出现时,做差,中间的长度就是和为0的区间
class Solution { public: int findMaxLength(vector & nums) { int i, n = nums.size(), sum = 0, maxlen = 0; unordered_mapm;//sum, 第一次出现sum时的idx m[0] = -1; for(i = 0; i < n; ++i) { if(nums[i]) sum += 1; else sum -= 1; if(!m.count(sum)) m[sum] = i; else maxlen = max(maxlen, i-m[sum]); } return maxlen; }};
344 ms 78.5 MB
转载地址:https://michael.blog.csdn.net/article/details/106157791 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月25日 22时22分30秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Eclipse及其插件下载网址大全
2019-05-01
正则表达式简介(微软)--6.优先权顺序
2019-05-01
多用户与多租户的区别
2019-05-01
Python自动化运维 - day14 - JavaScript基础
2019-05-02
oracle保存小数点前为"0"的问题
2019-05-02
linux sar 命令详解
2019-05-02
ipvsadm 安装配置
2019-05-02
Linux shell脚本的字符串截取
2019-05-02
数据库复习(4)
2019-05-02
1小时点击量破千万!阿里巴巴首发:MySQL高级调优笔记!全是技术重点
2019-05-02
这个GItHub上的Java项目开源了 2021最全的Java架构面试复习指南
2019-05-02
Proftpd MySQL [Step by Step]
2019-05-02
EFI Shell 命令参考
2019-05-02
HP-UX oracle RAC 双机实践
2019-05-02
解决SHELL脚本中的export无法生效的问题【转】
2019-05-02
linux中的sh脚本语法【转】
2019-05-02
区别数据结构中的堆栈与内存中的堆栈的个人总结【转】
2019-05-02
C++拷贝构造函数(深拷贝,浅拷贝)【转】
2019-05-02