首页 > 代码库 > [leetcode-525-Contiguous Array]
[leetcode-525-Contiguous Array]
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
Example 1:
Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
思路:
将0改为-1,将原题目改成求最大连续区间,区间内元素和为0。用map记录当前元素 j 和之前所有元素的和与下标,当map
中存在相同的sum时,说明之前i到j的区间元素和为0。
int findMaxLength(vector<int>& nums) { for (auto& a:nums) if (a == 0)a = -1; map<int, int>mp; mp[0] = -1; int sum = 0,ret =0; for (int i = 0; i < nums.size();i++) { sum += nums[i]; if (mp.count(sum))ret = max(ret, i - mp[sum]); else mp[sum] = i; } return ret; }
参考:
http://www.cnblogs.com/liujinhong/p/6472580.html
[leetcode-525-Contiguous Array]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。