Algorithm
Problem Name: 525. Contiguous Array
Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.
Example 1:
Input: nums = [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Example 2:
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 <= 105nums[i]is either0or1.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct elem_s {
int n;
int idx;
struct elem_s *shadow;
} elem_t;
#define SZ 10240
void free_set(elem_t **set, int sz) {
int i;
elem_t *e, *s;
for (i = 0; i < sz; i ++) {
e = set[i];
while (e) {
s = e->shadow;
free(e);
e = s;
}
}
}
void put(elem_t **set, int n, int idx) {
int k = n; //(n >= 0) ? n : -n;
elem_t *e = malloc(sizeof(elem_t));
e->n = n;
e->idx = idx;
e->shadow = set[k % SZ];
set[k % SZ] = e;
}
elem_t *lookup(elem_t **set, int n) {
int k = n; //(n >= 0) ? n : -n;
elem_t *e = set[k % SZ];
while (e && e->n != n) e = e->shadow;
return e;
}
int findMaxLength(int* nums, int numsSize) {
int n[2] = { 0 };
int i, d = 0;
elem_t *buff[SZ * 2] = { 0 };
elem_t *e, *set = &buff[SZ];
if (!numsSize) return 0;
put(set, 0, -1);
for (i = 0; i < numsSize; i ++) {
n[nums[i]] ++;
e = lookup(set, n[0] - n[1]);
if (!e) {
put(set, n[0] - n[1], i);
} else if (d < i - e->idx) {
d = i - e->idx;
}
}
free_set(buff, sizeof(buff)/sizeof(buff[0]));
return d;
}
Input
nums = [0,1]
Output
2
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int findMaxLength(vector<int>& nums) {
for(auto& x: nums) if(!x) x = -1;
unordered_map < int, int>m;
m[0] = -1;
int sum = 0, maxlen = 0;
for(int i = 0; i < nums.size(); i++){
sum += nums[i];
if(m.count(sum)) maxlen = max(maxlen, i - m[sum]);
else m[sum] = i;
}
return maxlen;
}
};
Input
nums = [0,1]
Output
2
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int findMaxLength(int[] nums) {
Map map = new HashMap<>();
map.put(0, -1);
int maxLength = 0;
int count = 0;
for (int i = 0; i < nums.length; i++) {
count += nums[i] == 0 ? -1 : 1;
if (map.containsKey(count)) {
maxLength = Math.max(maxLength, i - map.get(count));
} else {
map.put(count, i);
}
}
return maxLength;
}
}
Input
nums = [0,1,0]
Output
2
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const findMaxLength = function(nums) {
let res = 0, sum = 0
const hash = {0: -1}, n = nums.length
for(let i = 0; i < n; i++) {
const cur = nums[i]
sum += cur === 0 ? -1 : 1
if(hash[sum] != null) {
res = Math.max(res, i - hash[sum])
} else {
hash[sum] = i
}
}
return res
};
Input
nums = [0,1,0]
Output
2
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _0525_ContiguousArray
{
public int FindMaxLength(int[] nums)
{
var map = new Dictionary < int, int>();
map.Add(0, -1);
var maxlen = 0;
var count = 0;
for (int i = 0; i < nums.Length; i++)
{
count += nums[i] == 1 ? 1 : -1;
if (map.ContainsKey(count))
maxlen = Math.Max(maxlen, i - map[count]);
else
map.Add(count, i);
}
return maxlen;
}
}
}
Input
nums = [0,1]
Output
2