Contiguous Array Problem
Description
LeetCode Problem 525.
Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.
Example 1:
1
2
3
Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Example 2:
1
2
3
Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Constraints:
- 1 <= nums.length <= 10^5
- nums[i] is either 0 or 1.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int sum = 0, maxLen = 0;
unordered_map<int, int> seen{ {0, -1} };
for(int i = 0; i < nums.size(); i++) {
sum += nums[i]==1 ? 1 : -1;
if(seen.count(sum))
maxLen = max(maxLen, i-seen[sum]);
else
seen[sum] = i;
}
return maxLen;
}
};