【数据结构-前缀哈希】力扣525. 连续数组
创始人
2024-11-04 22:11:42

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。

示例 1:
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2:
输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

在这里插入图片描述

class Solution { public:     int findMaxLength(vector& nums) {         for(int &num : nums){             if(num == 0){                 num = -1;             }         }             int sum = 0,res = 0;         unordered_map group;         for(int i = 0;i < nums.size();i++){             sum += nums[i];             if(sum == 0){                 res = i + 1;             }             if(group.contains(sum)){                 res = max(res, i - group[sum]);             }             else{                 group[sum] = i;             }         }         return res;     } }; 

时间复杂度:O(n),其中 n 是数组 nums 的长度。需要遍历数组一次。
空间复杂度:O(n)

将nums中的0全部替换成-1,然后定义一个哈希表group,键用来储存sum,值用来储存对应的前缀和的下标。当前计算前缀和sum的时候,如果前面有相同的前缀和,说明中间这个子段和为0,也就说明0和1的数量相等,所以这个时候i - group[sum]来求这个子段的长度。然后不断比较求的0和1数量相等的最大子段长度。

相关内容

热门资讯

裸辞做“一人公司”,我后悔了 去年这个时候,一位以色列程序员正在东南亚旅行。他顺手把一个在脑子里转了很久的想法做成了产品,一个让任...
南京建成国内首个Pre-6G试... 4月21日,2026全球6G技术与产业生态大会在南京开幕。全息互动技术展台前,一名远在北京的工作人员...
超梵求职受邀参加“2025抖音... 超梵求职受邀参加“2025抖音巨量引擎成人教育行业生态大会”,探讨分享优质内容传播,服务万千学员。 ...
摩托罗拉Razr 2026(R... IT之家 4 月 22 日消息,摩托罗拉宣布新一代 Razr 折叠手机将于 4 月 29 日在美国发...
库克卸任,特纳斯领航:苹果新纪... 苹果首席执行官蒂姆·库克将卸任,硬件工程主管约翰·特纳斯将接任,苹果公司今天宣布此事。 库克将在夏季...