专栏首页Michael阿明学习之路LeetCode 525. 连续数组(前缀和+哈希)

LeetCode 525. 连续数组(前缀和+哈希)

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<int>& nums) {
    	int i, n = nums.size(), sum = 0, maxlen = 0;
    	unordered_map<int,int> m;//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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 209. 长度最小的子数组(滑动窗口)

    给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。 如果不存在符合条件的连续子数组,返回 0。

    Michael阿明
  • LeetCode 1292. 元素和小于等于阈值的正方形的最大边长(DP)

    请你返回元素总和小于或等于阈值的正方形区域的最大边长; 如果没有这样的正方形区域,则返回 0 。

    Michael阿明
  • LeetCode 494. 目标和(DFS+DP)

    给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符...

    Michael阿明
  • 【每天一道编程系列-2018.3.7】(Ans)

      Given an array S of n integers, find three integers in S such that the sum is ...

    yesr
  • O(n)时间的排序

    题目:某公司有几万名员工,请完成一个时间复杂度为O(n)的算法对该公司员工的年龄作排序,可使用O(1)的辅助空间。      题目特别强调是对一个公司的员工的年...

    猿人谷
  • Golang Leetcode 560. Subarray Sum Equals K.go

    更多内容请移步我的repo:https://github.com/anakin/golang-leetcode

    anakinsun
  • Go语言的管道Channel用法实例

    本文实例讲述了Go语言的管道Channel用法。分享给大家供大家参考。具体分析如下: channel 是有类型的管道,可以用 channel 操作符 <- 对其...

    李海彬
  • 最小子数组

    一份执着✘
  • LeetCode 523. 连续的子数组和(求余 哈希)

    给定一个包含非负数的数组和一个目标整数 k,编写一个函数来判断该数组是否含有连续的子数组,其大小至少为 2,总和为 k 的倍数,即总和为 n*k,其中 n 也是...

    Michael阿明
  • 爬虫带你了解一下Golang的市场行情

    项目地址:https://github.com/go-crawler/lagou_jobs

    李海彬

扫码关注云+社区

领取腾讯云代金券